Height of Binary Tree in DSA C

Mental Model

The height of a binary tree is the longest path from the root to any leaf node. It tells us how tall the tree is.

Analogy: Imagine a family tree where the height is how many generations there are from the oldest ancestor (root) down to the youngest descendant (leaf).

      1
     / \
    2   3
   / 
  4  

(Height is the longest path from 1 down to 4)

Dry Run Walkthrough

Input: Binary tree: 1 -> 2 -> 4 (left child), 1 -> 3 (right child)

Goal: Find the height of the tree, which is the longest path from root to leaf

Step 1: Start at root node 1, check left subtree height

At node 1 ↑
Tree: 1 -> 2 -> 4, 1 -> 3

Why: We need to find height of left subtree to compare with right subtree

Step 2: At node 2, check left subtree height

At node 2 ↑
Subtree: 2 -> 4

Why: Continue down left to find leaf depth

Step 3: At node 4, no children, height is 1

At leaf node 4 ↑
Subtree: 4

Why: Leaf node height is 1

Step 4: Back to node 2, left height is 1, right is 0, so height is 1 + max(1,0) = 2

At node 2 ↑
Height calculated as 2

Why: Height includes current node plus max height of children

Step 5: At node 1, check right subtree height at node 3

At node 3 ↑
Subtree: 3

Why: Check right subtree height to compare

Step 6: Node 3 is leaf, height is 1

At leaf node 3 ↑
Height is 1

Why: Leaf node height is 1

Step 7: Back to node 1, left height 2, right height 1, total height is 1 + max(2,1) = 3

At root node 1 ↑
Height calculated as 3

Why: Height of tree is root plus max height of subtrees

Result:

1 -> 2 -> 4 (height 3), 1 -> 3 (height 1)
Final height: 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define node structure
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

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

// Function to find height of binary tree
int height(Node* root) {
    if (root == NULL) {
        return 0; // empty tree has height 0
    }
    int leftHeight = height(root->left); // height of left subtree
    int rightHeight = height(root->right); // height of right subtree
    if (leftHeight > rightHeight) {
        return leftHeight + 1; // add current node
    } else {
        return rightHeight + 1; // add current node
    }
}

int main() {
    // Build tree from dry run example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);

    int h = height(root);
    printf("Height of tree: %d\n", h);
    return 0;
}

if (root == NULL) { return 0; }

base case: empty subtree has height 0

int leftHeight = height(root->left);

recursively find height of left subtree

int rightHeight = height(root->right);

recursively find height of right subtree

if (leftHeight > rightHeight) { return leftHeight + 1; } else { return rightHeight + 1; }

height is current node plus max of left and right subtree heights

Output

Height of tree: 3

Complexity Analysis

Time: O(n) because we visit every node once to calculate height

Space: O(h) where h is tree height due to recursion call stack

vs Alternative: Iterative methods exist but recursion is simpler and intuitive for tree height

Edge Cases

Empty tree (root is NULL)

Returns height 0 correctly

DSA C

if (root == NULL) { return 0; }

Single node tree

Returns height 1 as only root exists

DSA C

if (root == NULL) { return 0; }

Unbalanced tree (all nodes on one side)

Returns height equal to number of nodes on that side

DSA C

int leftHeight = height(root->left); int rightHeight = height(root->right);

When to Use This Pattern

When you need to find the longest path from root to leaf in a tree, use the height calculation pattern with recursion to explore subtrees.

Common Mistakes

Mistake: Returning 0 for leaf nodes instead of 1
Fix: Return 0 only for NULL nodes; leaf nodes return 1 as height

Mistake: Adding left and right heights instead of taking max
Fix: Use max of left and right subtree heights plus 1 for current node

Summary

Calculates the longest path from root to any leaf node in a binary tree.

Use when you need to know how tall or deep a tree is.

The height is 1 plus the maximum height of its left and right subtrees.

Practice

1. What is the height of a binary tree with only one node (the root)?

easy

A. 0

B. 1

C. 2

D. Undefined

Solution

1. Step 1: Understand height definition

   The height of a binary tree is the number of edges on the longest path from the root to a leaf.

2. Step 2: Apply to single node tree

   With only one node (root), the longest path has length 0 edges.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Height of single node tree = 0 [OK]

Hint: Height counts edges on longest root-to-leaf path [OK]

Common Mistakes:

• Thinking height is 1 for single node
• Confusing height with number of nodes
• Assuming height is undefined for single node

2. Which of the following is the correct C function signature to calculate the height of a binary tree node?

easy

A. void height(struct Node root);

B. int height(Node root);

C. int height(struct Node* root);

D. int height(struct Node root);

Solution

1. Step 1: Check parameter type for tree node

   In C, a tree node is usually passed as a pointer to struct Node.

2. Step 2: Check return type and parameter correctness

   The function returns an int (height) and takes a pointer to struct Node.

3. Final Answer:

   int height(struct Node* root); -> Option C

4. Quick Check:

   Correct signature uses pointer to struct Node [OK]

Hint: Use pointer to struct Node for tree parameters [OK]

Common Mistakes:

• Passing struct Node by value instead of pointer
• Using void return type instead of int
• Missing struct keyword in parameter

3. What is the output of the following code snippet calculating the height of this binary tree?

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

int height(struct Node* root) {
  if (root == NULL) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// Tree:
//     10
//    /  \
//   5    15
//        /
//       12

int main() {
  struct Node n12 = {12, NULL, NULL};
  struct Node n15 = {15, &n12, NULL};
  struct Node n5 = {5, NULL, NULL};
  struct Node n10 = {10, &n5, &n15};
  printf("%d", height(&n10));
  return 0;
}

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Trace left subtree height

   Left subtree of root (10) has node 5 only, height = 1.

2. Step 2: Trace right subtree height

   Right subtree has nodes 15 and 12. Height is 2 (15 -> 12).

3. Step 3: Calculate total height

   Height = max(1, 2) + 1 (for root) = 3.

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Height = 3 [OK]

Hint: Height = max(left, right) + 1 recursively [OK]

Common Mistakes:

• Counting edges instead of nodes
• Ignoring one subtree height
• Off-by-one error in return statement

4. Identify the error in this height function and select the correct fix:

int height(struct Node* root) {
  if (root == NULL) return -1;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

medium

A. Change base case return from -1 to 1

B. Change base case return from -1 to 0

C. Remove +1 from return statement

D. Change recursive calls to root->right and root->left swapped

Solution

1. Step 1: Understand base case meaning

   Base case returns height for empty tree. Returning -1 means height counts edges, not nodes.

2. Step 2: Fix base case for node count height

   To count nodes, base case should return 0 for NULL.

3. Final Answer:

   Change base case return from -1 to 0 -> Option B

4. Quick Check:

   Base case 0 for NULL node height [OK]

Hint: Base case for NULL should return 0 for node height [OK]

Common Mistakes:

• Returning -1 causes off-by-one height
• Removing +1 leads to wrong height
• Swapping left and right recursive calls unnecessary

5. Given a binary tree where each node has either 0 or 2 children, what is the height of a full binary tree with 7 nodes? Select the correct height.

hard

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Understand full binary tree properties

   A full binary tree with all nodes having 0 or 2 children has nodes count = 2^h - 1, where h is height.

2. Step 2: Calculate height from nodes count

   Given nodes = 7, solve 2^h - 1 = 7 -> 2^h = 8 -> h = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Full binary tree height for 7 nodes = 3 [OK]

Hint: Full tree nodes = 2^height - 1 formula [OK]

Common Mistakes:

• Confusing height with number of edges
• Using incomplete binary tree formula
• Miscounting nodes or height