ISI 2019 | PCB CS | Question: 4

Question

In a binary tree $T$, for a node $v$, the $\text{LEFT-HEIGHT} (v)$ is the length of the longest path from $v$ to any leaf in the left subtree of $v$. If $v$ has no left child then $\text{LEFT-HEIGHT} (v)=0$. The $\text{RIGHT-HEIGHT} (v)$ is defined accordingly.

A node $v$ is said to be properly balanced if $$ \mid \operatorname{LEFT-HEIGHT}(v)-\text { RIGHT-HEIGHT }(v) \mid \leq 1 \text {. } $$ Design an efficient algorithm that, given a binary tree, enumerates all the nodes which are properly balanced.

Answer 1

A node \( v \) in a binary tree is defined as properly balanced if the absolute difference between its left height and right height is at most 1, i.e., 

\[ |\text{LEFT-HEIGHT}(v) - \text{RIGHT-HEIGHT}(v)| \leq 1 \] 

Our goal is to identify all such nodes efficiently, ideally in \( O(n) \) time, where \( n \) is the number of nodes in the tree.

Bottom-Up Height Computation

Since we need to determine the left and right heights for every node and check the balance condition, a naive approach—computing heights from scratch for each node—would take \( O(n) \) time per node, leading to an \( O(n^2) \) algorithm. 😕

To achieve efficiency, we can compute heights in a bottom-up manner using a post-order traversal. In a post-order traversal, we process a node’s left child, then its right child, and finally the node itself. This allows us to compute the height of a subtree once and reuse it when evaluating the parent node.😀

Algorithm Design and Plannig 

We can design a recursive algorithm that:
1. Computes the height of each subtree rooted at a node.
2. Uses these heights to check the balance condition at each node.
3. Collects all nodes that are properly balanced.   Simple 😉

NOTE: The height of a subtree rooted at a node is defined as the length of the longest path from that node to a leaf in its subtree, which is 1 plus the maximum of the left and right heights (or 0 if the node is a leaf or NULL). For a NULL node (no subtree), the height is 0, match with  problem’s convention that the height is 0 when there is no child.

To enumerate the balanced nodes, we can accumulate them in a list during the traversal. We’ll use a recursive function that returns the height of the subtree and, as a side effect, appends properly balanced nodes to a shared list.

- Input: A binary tree \( T \) with a root node.
- Output: A list of all nodes in \( T \) that are properly balanced.
- Data Structure: A list `balanced_nodes` to store the properly balanced nodes, accessible across recursive calls.

Procedure
1. Initialize an empty list `balanced_nodes`.
2. Call `computeHeightAndCheckBalance(root, balanced_nodes)` recurssive function on the root of the tree \( T \).

• which use a post-order traversal to compute the heights of the left and right subtrees for each node.
• For each node, checking if the absolute difference between its left height and right height is less than or equal to 1.
• Collect the nodes that satisfy this condition in a list during the traversal.

3. After the call completes, `balanced_nodes` contains all properly balanced nodes.
4. Return or process `balanced_nodes` as needed 

 

// Recursive function to compute height and check balance
int computeHeightAndCheckBalance(node, balanced_nodes) 
{
    // Base case: empty subtree
    if (node == NULL) {
        return 0
    }

    // Recursively compute left height
    left_height = computeHeightAndCheckBalance(node->left, balanced_nodes)
    
    // Recursively compute right height
    right_height = computeHeightAndCheckBalance(node->right, balanced_nodes)
    
    // Check if the node is properly balanced
    if (abs(left_height - right_height) <= 1) {
        addBalancedNode(balanced_nodes, node)
    }
    
    // Compute the height of the current node
    height = 1 + (left_height > right_height ? left_height : right_height)
    
    return height
}


// Add a node to the balanced nodes list
void addBalancedNode(list,  node) 
{
    if (list->count >= list->capacity) 
    {
        // Simple handling: in practice, resize the array
        print("Balanced nodes array is full!\n")
        return;
    }
    list->nodes[list->count] = node;
    list->count++;
}

 

Complexity Analysis

Time Complexity: The algorithm performs a post-order traversal, visiting each node exactly once. At each node, it performs constant-time operations: two recursive calls (processed once per node), a balance check, and possibly appending to the list. Thus, the total time is \( O(n) \), where \( n \) is the number of nodes.
Space Complexity:  The recursion stack depth is equal to the height of the tree, which is \( O(h) \), where \( h \) is the tree’s height. In the worst case (e.g., a skewed tree), \( h = n \), so \( O(n) \).

•   The `balanced_nodes` list stores up to \( n \) nodes, requiring \( O(n) \) space.
•   Total space complexity is \( O(n) \).

Comments

Recursive Function: `computeHeightAndCheckBalance(node, balanced_nodes)`
Base Case:
  - If `node` is `None` (an empty subtree), 

               return 0 (height of an empty subtree).
Recursive Steps:
  1. Left Subtree: Recursively call `computeHeightAndCheckBalance` on the left child to get `left_height`.
     - If there is no left child, this returns 0, matching \( \text{LEFT-HEIGHT} = 0 \).

  2. Right Subtree: Recursively call `computeHeightAndCheckBalance` on the right child to get `right_height`.
     - If there is no right child, this returns 0, matching \( \text{RIGHT-HEIGHT} = 0 \).

  3. Check Balance: Compute \( |\text{left_height} - \text{right_height}| \).
     - If this difference is less than or equal to 1, the current `node` is properly balanced, so append it to `balanced_nodes`.
  4. Compute Height: The height of the current subtree is \( 1 + \max(\text{left_height}, \text{right_height}) \).
     - This represents the longest path from the node to any leaf in its subtree.
  5. Return: Return the computed height.

 
Example 
Consider a simple tree:

Node D: Leaf node.
  - Left height = 0,       Right height = 0.
  - \( |0 - 0| = 0 \leq 1 \), so D is balanced.                       Height = \( 1 + \max(0, 0) = 1 \).
 

Node B: Left child is D,              no right child.
  - Left height = 1,               Right height = 0.
  - \( |1 - 0| = 1 \leq 1 \), so B is balanced.                      Height = \( 1 + \max(1, 0) = 2 \).
 

Node C: No children.
  - Left height = 0,            Right height = 0.
  - \( |0 - 0| = 0 \leq 1 \), so C is balanced.                      Height = \( 1 + \max(0, 0) = 1 \).
 

Node A: Left child is B,          right child is C.
  - Left height = 2,              Right height = 1.
  - \( |2 - 1| = 1 \leq 1 \), so A is balanced.                       Height = \( 1 + \max(2, 1) = 3 \).

All nodes (A, B, C, D) are properly balanced, and the algorithm correctly identifies them.

---

C implementation
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// Define the structure for a binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Define a structure to store balanced nodes and track count
struct BalancedNodes {
    struct Node** nodes; // Array of node pointers
    int count;          // Number of balanced nodes
    int capacity;       // Capacity of the array
};

// Create a new tree node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Initialize the balanced nodes list
struct BalancedNodes* initBalancedNodes(int capacity) {
    struct BalancedNodes* list = (struct BalancedNodes*)malloc(sizeof(struct BalancedNodes));
    list->nodes = (struct Node**)malloc(capacity * sizeof(struct Node*));
    list->count = 0;
    list->capacity = capacity;
    return list;
}

// Add a node to the balanced nodes list
void addBalancedNode(struct BalancedNodes* list, struct Node* node) {
    if (list->count >= list->capacity) {
        // Simple handling: in practice, resize the array
        printf("Balanced nodes array is full!\n");
        return;
    }
    list->nodes[list->count] = node;
    list->count++;
}

// Recursive function to compute height and check balance
int computeHeightAndCheckBalance(struct Node* node, struct BalancedNodes* balanced_nodes) {
    // Base case: empty subtree
    if (node == NULL) {
        return 0;
    }

    // Recursively compute left height
    int left_height = computeHeightAndCheckBalance(node->left, balanced_nodes);
    
    // Recursively compute right height
    int right_height = computeHeightAndCheckBalance(node->right, balanced_nodes);
    
    // Check if the node is properly balanced
    if (abs(left_height - right_height) <= 1) {
        addBalancedNode(balanced_nodes, node);
    }
    
    // Compute the height of the current node
    int height = 1 + (left_height > right_height ? left_height : right_height);
    
    return height;
}

// Main function to enumerate balanced nodes
void enumerateBalancedNodes(struct Node* root) {
    // Initialize balanced nodes list (assuming max n nodes)
    struct BalancedNodes* balanced_nodes = initBalancedNodes(100); // Adjust capacity as needed
    
    // Compute heights and collect balanced nodes
    computeHeightAndCheckBalance(root, balanced_nodes);
    
    // Print the balanced nodes
    printf("Properly balanced nodes (by data): ");
    if (balanced_nodes->count == 0) {
        printf("None\n");
    } else {
        for (int i = 0; i < balanced_nodes->count; i++) {
            printf("%d", balanced_nodes->nodes[i]->data);
            if (i < balanced_nodes->count - 1) {
                printf(", ");
            }
        }
        printf("\n");
    }
    
    // Free allocated memory
    free(balanced_nodes->nodes);
    free(balanced_nodes);
}

// Utility function to free the tree
void freeTree(struct Node* node) {
    if (node == NULL) {
        return;
    }
    freeTree(node->left);
    freeTree(node->right);
    free(node);
}

// Main function for testing
int main() {
    // Example tree:
    //       1
    //      / \
    //     2   3
    //    /
    //   4
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    
    enumerateBalancedNodes(root);
    
    // Free the tree
    freeTree(root);
    
    return 0;
}