Height of Binary Tree in DSA C++ - Time & Space Complexity

Time Complexity: Height of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to find the height of a binary tree as the tree grows.

How does the time needed change when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the height of a binary tree by checking the height of left and right subtrees recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Once per node in the tree.

How Execution Grows With Input

Each node is visited once, so the time grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The time grows linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the height grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The height calculation only depends on the longest path, so it should be faster than visiting all nodes."

[OK] Correct: To find the longest path, the function must check every node to be sure no taller path exists, so it visits all nodes.

Interview Connect

Understanding this helps you explain how recursive tree algorithms work and why visiting all nodes is often necessary.

Self-Check

"What if the tree was a balanced binary tree? How would the time complexity change?"

Practice

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

easy

A. 2

B. Undefined

C. 1

D. 0

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 D

4. Quick Check:

   Single node tree height = 0 [OK]

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

Common Mistakes:

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

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

easy

A. int height(Node* root);

B. void height(Node root);

C. int height(Node root);

D. Node height(Node* root);

Solution

1. Step 1: Identify return type

   The height function returns an integer representing height, so return type is int.

2. Step 2: Identify parameter type

   Binary tree nodes are usually passed as pointers to avoid copying, so parameter is Node* root.

3. Final Answer:

   int height(Node* root); -> Option A

4. Quick Check:

   Return int, parameter Node pointer [OK]

Hint: Height returns int, takes pointer to Node [OK]

Common Mistakes:

• Using void return type
• Passing Node by value
• Returning Node instead of int

3. What is the output of the following C++ code snippet?

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

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

int main() {
  Node n1 = {1, nullptr, nullptr};
  Node n2 = {2, nullptr, nullptr};
  Node n3 = {3, &n1, &n2};
  std::cout << height(&n3);
  return 0;
}

medium

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Analyze tree structure

   Root n3 has two children n1 and n2, both leaves with height 1.

2. Step 2: Calculate height recursively

   Height of n1 and n2 is 1, so height of n3 = 1 + max(1,1) = 2.

3. Step 3: Confirm output

   The code prints height(&n3), which is 2.

4. Final Answer:

   2 -> Option C

5. Quick Check:

   Height = 2 [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Returning 0 for non-empty tree
• Misreading tree structure

4. Identify the error in the following height function for a binary tree:

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

medium

A. Base case should return 0, not -1

B. Function should return Node*, not int

C. Missing check for leaf nodes

D. Incorrect use of ternary operator

Solution

1. Step 1: Check base case return value

   Returning -1 for nullptr causes height to be off by one.

2. Step 2: Correct base case

   Base case should return 0 for empty tree to count height correctly.

3. Final Answer:

   Base case should return 0, not -1 -> Option A

4. Quick Check:

   Base case = 0 for empty tree [OK]

Hint: Base case for empty node returns 0 height [OK]

Common Mistakes:

• Returning -1 causes negative height
• Ignoring nullptr check
• Wrong return type

5. Given a binary tree where some nodes have only one child, what is the height of the tree below?

       10
      /  
     5    
      \   
       7  
        \
         9

hard

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Trace longest path from root to leaf

   Path is 10 -> 5 -> 7 -> 9, which has 4 nodes and 3 edges.

2. Step 2: Count edges on path

   Counting edges: 10-5 (1), 5-7 (2), 7-9 (3).

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Longest path length = 3 edges [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Ignoring missing left child
• Assuming height is number of levels with both children