Height of Binary Tree in DSA Java

Mental Model

The height of a binary tree is the longest path from the root to any leaf node, counting edges or nodes along the way.

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

      1
     / \
    2   3
   / 
  4  

Here, the root is 1, and the height is the longest path down to a leaf (node 4).

Dry Run Walkthrough

Input: Binary tree: root=1, left=2, right=3, left of 2=4

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

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

1 -> left subtree root 2 -> right subtree root 3

Why: We need to find height of left and right subtrees to compare

Step 2: At node 2, check left subtree height

2 -> left child 4 -> no right child

Why: Node 2 has a left child, so we go deeper to find height

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

4 -> null left and right

Why: Leaf node height is 1

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

2 -> height 2

Why: Height counts the longest path down from this node

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

3 -> null left and right

Why: Leaf node height is 1

Step 6: Back to root 1, left height is 2, right height is 1, so height is 1 + max(2,1) = 3

1 -> height 3

Why: Height of tree is longest path from root to leaf

Result:

1 -> height 3
The height of the tree is 3

Annotated Code

DSA Java

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

public class BinaryTreeHeight {
    // Function to find height of binary tree
    public static int height(Node root) {
        if (root == null) {
            return 0; // base case: empty tree has height 0
        }
        int leftHeight = height(root.left); // find height of left subtree
        int rightHeight = height(root.right); // find height of right subtree
        return 1 + Math.max(leftHeight, rightHeight); // height is 1 + max of left/right
    }

    public static void main(String[] args) {
        // Construct the tree from dry run example
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);

        int treeHeight = height(root);
        System.out.println("Height of the tree is " + treeHeight);
    }
}

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

return 1 + Math.max(leftHeight, rightHeight);

height is 1 plus the larger of left or right subtree heights

Output

Height of the tree is 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 stack

vs Alternative: Compared to iterative approaches, recursion is simpler but uses stack space; iterative may use explicit stack but same time complexity

Edge Cases

Empty tree (root is null)

Returns height 0 as there are no nodes

DSA Java

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

Single node tree

Returns height 1 since only root exists

DSA Java

return 1 + Math.max(leftHeight, rightHeight);

Skewed tree (all nodes only on one side)

Height equals number of nodes in the longest path

DSA Java

return 1 + Math.max(leftHeight, rightHeight);

When to Use This Pattern

When asked for the longest path or depth in a tree, use the height pattern by recursively checking left and right subtrees and taking the maximum.

Common Mistakes

Mistake: Returning sum of left and right subtree heights instead of max
Fix: Use Math.max(leftHeight, rightHeight) to get longest path, not sum

Mistake: Not handling null root and causing null pointer errors
Fix: Add base case to return 0 when root is null

Summary

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

Use it when you need to know the depth or height of a tree structure.

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. 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