Height of Binary Tree in DSA Java - Execution Trace

Concept Flow - Height of Binary Tree

Start at root node

↓

Is node null?

Yes→Return 0

No↓

Compute height of left subtree

↓

Compute height of right subtree

↓

Height = max(left, right) + 1

↓

Return height

The height is found by recursively checking left and right subtrees, then taking the larger height plus one for the current node.

Execution Sample

DSA Java

int height(Node node) {
  if (node == null) return 0;
  int leftHeight = height(node.left);
  int rightHeight = height(node.right);
  return Math.max(leftHeight, rightHeight) + 1;
}

This code calculates the height of a binary tree by recursively finding the height of left and right children and returning the larger plus one.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Computed	Visual State
1	Visit root	1	-	-	-	1 / \ 2 3
2	Visit left child	2	-	-	-	1 / \ 2 3
3	Visit left.left	4	-	-	-	1 / \ 2 3 / 4
4	Left.left is leaf, return 1	4	0	0	1	1 / \ 2 3 / 4
5	Visit left.right	5	-	-	-	1 / \ 2 3 / \ 4 5
6	Left.right is leaf, return 1	5	0	0	1	1 / \ 2 3 / \ 4 5
7	Compute height at node 2	2	1	1	2	1 / \ 2(2) 3 / \ 4 5
8	Visit right child	3	-	-	-	1 / \ 2(2) 3 / \ 4 5
9	Visit right.left	6	-	-	-	1 / \ 2(2) 3 / \ 4 5 /
10	Right.left is leaf, return 1	6	0	0	1	1 / \ 2(2) 3 / \ 4 5 /
11	Visit right.right	7	-	-	-	1 / \ 2(2) 3 / \ 4 5 / \ 6 7
12	Right.right is leaf, return 1	7	0	0	1	1 / \ 2(2) 3 / \ 4 5 / \ 6 7
13	Compute height at node 3	3	1	1	2	1 / \ 2(2) 3(2) / \ 4 5 / \ 6 7
14	Compute height at root	1	2	2	3	1(3) / \ 2(2) 3(2) / \ 4 5 / \ 6 7
15	Return final height	1	2	2	3	1(3) / \ 2(2) 3(2) / \ 4 5 / \ 6 7

💡 All nodes visited; height computed as 3 at root node

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 10	After Step 12	After Step 13	After Step 14	Final
node	1	4	5	2	6	7	3	1	1
leftHeight	-	0	0	1	0	0	1	2	2
rightHeight	-	0	0	1	0	0	1	2	2
height	-	1	1	2	1	1	2	3	3

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Returning 0 for a null node means that an empty subtree has height 0, which is the base case stopping recursion (see Step 4 and Step 10 in execution_table).

Why do we add 1 after taking max of left and right heights?

We add 1 to count the current node itself, so height includes the node plus the tallest subtree below it (see Step 7, 13, and 14).

How does recursion ensure all nodes are visited?

The function calls itself on left and right children until it reaches null nodes, ensuring every node is processed (see Steps 2, 3, 5, 9, 11).

Visual Quiz - 3 Questions

Look at the execution_table, what is the height computed at node 2 (Step 7)?

A 3

B 1

C 2

D 0

💡 Hint

Check the 'Height Computed' column at Step 7 in execution_table

At which step does the recursion return 0 for a null node?

A Step 14

B Step 4

C Step 7

D Step 1

💡 Hint

Look for steps where 'Left Height' and 'Right Height' are 0 and node is a leaf (Step 4 or Step 10)

If the tree had only root node, what would be the final height?

A 1

B 0

C 2

D 3

💡 Hint

Height counts nodes along longest path; single node means height 1 (see final height at root in execution_table)

Concept Snapshot

Height of Binary Tree:
- Base case: null node returns 0
- Recursively find left and right subtree heights
- Height = max(left, right) + 1
- Counts nodes along longest path from root to leaf
- Uses post-order traversal (left, right, node)

Full Transcript

To find the height of a binary tree, start at the root node. If the node is null, return 0 as the height. Otherwise, recursively find the height of the left subtree and the right subtree. The height of the current node is the maximum of these two heights plus one to include the current node itself. This process continues until all nodes are visited. The final height is the number of nodes along the longest path from the root to a leaf node. The recursion uses post-order traversal, visiting left and right children before computing the current node's height.

Practice

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

easy

A. Undefined

B. 1

C. 2

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 1 for single node
• Confusing height with number of nodes
• Assuming height undefined for single node

2. Which of the following Java method signatures correctly defines a recursive method to find the height of a binary tree node?

easy

A. public int height(Node root)

B. int height(Node root) void

C. public void height(Node root) returns int

D. height(Node root) int public

Solution

1. Step 1: Check Java method syntax

   Java methods must specify access modifier, return type, method name, and parameters correctly.

2. Step 2: Validate each option

   public int height(Node root) follows correct syntax: public int height(Node root). Others have syntax errors.

3. Final Answer:

   public int height(Node root) -> Option A

4. Quick Check:

   Correct Java method signature = public int height(Node root) [OK]

Hint: Java method: access + return type + name + parameters [OK]

Common Mistakes:

• Wrong order of return type and name
• Missing return type
• Using void with return value

3. What will be the output of the following Java code snippet?

class Node {
  int data;
  Node left, right;
  Node(int d) { data = d; left = right = null; }
}

public class Test {
  public static int height(Node root) {
    if (root == null) return 0;
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
  }

  public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    System.out.println(height(root));
  }
}

medium

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Visualize the tree structure

   The tree has root 1, left child 2, right child 3, and left child of 2 is 4. The longest path is 1->2->4.

2. Step 2: Calculate height recursively

   Height is max depth: left subtree height = 2 (nodes 2->4), right subtree height = 1 (node 3), so total height = max(2,1)+1 = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Longest path length = 3 [OK]

Hint: Height = longest root-to-leaf path node count [OK]

Common Mistakes:

• Counting edges instead of nodes
• Ignoring null child base case
• Misreading tree structure

4. Identify the error in the following Java method to find the height of a binary tree:

public int height(Node root) {
  if (root == null) {
    return -1;
  }
  int leftHeight = height(root.left);
  int rightHeight = height(root.right);
  return Math.max(leftHeight, rightHeight);
}

medium

A. The method should not use recursion.

B. The method should return the sum of left and right heights.

C. The base case should return 0, not -1.

D. The method should return the minimum of left and right heights.

Solution

1. Step 1: Check base case return value

   Height of empty tree (null) should be 0 or consistent with counting edges. Returning -1 causes incorrect height calculation.

2. Step 2: Check return statement

   Method returns max of left and right heights but misses adding 1 for current node, so height is underestimated.

3. Final Answer:

   The base case should return 0, not -1. -> Option C

4. Quick Check:

   Base case must return 0 for correct height [OK]

Hint: Base case return 0, add 1 after max height [OK]

Common Mistakes:

• Returning -1 in base case
• Not adding 1 to max height
• Returning sum instead of max

5. Given a binary tree where each node stores an integer, write a method to find the height of the tree and then print all nodes at the maximum height level. Which approach correctly combines these tasks?

hard

A. First find height recursively, then use a level-order traversal to print nodes at that height.

B. Print nodes during height calculation without storing height separately.

C. Use in-order traversal to print nodes at maximum height level directly.

D. Calculate height by counting nodes and print nodes at root only.

Solution

1. Step 1: Find height recursively

   Use a recursive method to find the height of the tree, which gives the maximum depth level.

2. Step 2: Use level-order traversal

   Perform a breadth-first traversal (level-order) and print nodes only at the level equal to the height found.

3. Final Answer:

   First find height recursively, then use a level-order traversal to print nodes at that height. -> Option A

4. Quick Check:

   Separate height calculation + level-order print = First find height recursively, then use a level-order traversal to print nodes at that height. [OK]

Hint: Find height first, then print nodes at that level [OK]

Common Mistakes:

• Trying to print during height recursion
• Using in-order traversal for level nodes
• Printing root only ignoring height