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. 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 with left child 2, right child 3; 2 has left child 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 height of left subtree

At node 1 ↑
Tree:
      1
     / \
    2   3
   / 
  4  

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

Step 2: At node 2, check height of left subtree

At node 2 ↑
Subtree:
    2
   / 
  4  

Why: Continue down left to find longest path

Step 3: At node 4, check left and right children which are null

At node 4 ↑
Leaf node with no children

Why: Leaf node height is 0, base case for recursion

Step 4: Return height 0 for node 4, go back to node 2 and check right child which is null

Back at node 2 ↑
Left height = 0, right height = -1 (null)

Why: Right child missing means height -1 or 0 depending on convention; here we treat null as -1

Step 5: Calculate height at node 2 as max(left, right) + 1 = max(0, -1) + 1 = 1

Height at node 2 is 1

Why: Height counts edges down to leaf, so add 1 for current node

Step 6: At node 1, check height of right subtree (node 3)

At node 3 ↑
Leaf node with no children

Why: Check right subtree height to compare with left

Step 7: Return height 0 for node 3 (leaf), compare with left height 1 at node 1

At node 1 ↑
Left height = 1, Right height = 0

Why: Height of tree is max of left and right subtree heights plus 1

Step 8: Calculate height at root node 1 as max(1, 0) + 1 = 2

Height of tree is 2

Why: Final height is longest path from root to leaf

Result:

      1
     / \
    2   3
   / 
  4  

Height = 2

Annotated Code

DSA C#

using System;

class Node
{
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree
{
    public Node root;

    // Function to find height of binary tree
    public int Height(Node node)
    {
        if (node == null)
            return -1; // base case: empty tree has height -1

        int leftHeight = Height(node.left); // height of left subtree
        int rightHeight = Height(node.right); // height of right subtree

        return Math.Max(leftHeight, rightHeight) + 1; // max height plus current node
    }

    static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);

        int height = tree.Height(tree.root);
        Console.WriteLine("Height of tree is " + height);
    }
}

if (node == null) return -1; // base case: empty tree has height -1

return -1 for null means leaf nodes have height 0

int leftHeight = Height(node.left); // height of left subtree

recursively find height of left subtree

int rightHeight = Height(node.right); // height of right subtree

recursively find height of right subtree

return Math.Max(leftHeight, rightHeight) + 1; // max height plus current node

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

Output

Height of tree is 2

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: Iterative approaches exist but recursive is simpler and intuitive; iterative may use explicit stack with similar time and space

Edge Cases

Empty tree (root is null)

Returns height -1 indicating no nodes

DSA C#

if (node == null)
    return -1;

Single node tree

Returns height 0 because root is also leaf

DSA C#

if (node == null)
    return -1;

Tree with only left or only right children

Correctly calculates height by following longest path

DSA C#

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

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

Common Mistakes

Mistake: Returning 0 for null nodes causes leaf height to be 1 instead of 0
Fix: Return -1 for null nodes so leaf nodes have height 0

Mistake: Adding left and right heights instead of max causes wrong height
Fix: Use max of left and right subtree heights plus 1

Summary

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

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

The height is the maximum height of left or right subtree plus one for the current node.

Practice

1. What does the height of a binary tree represent?

easy

A. The number of edges on the longest path from root to a leaf

B. The total number of nodes in the tree

C. The number of leaf nodes in the tree

D. The number of children of the root node

Solution

1. Step 1: Understand the definition of height in a binary tree

   The height is defined as the longest path from the root node down to the farthest leaf node, counted by edges.

2. Step 2: Compare with other options

   Other options describe different properties: total nodes, leaf count, or root children, which are not height.

3. Final Answer:

   The number of edges on the longest path from root to a leaf -> Option A

4. Quick Check:

   Height = longest root-to-leaf edge count [OK]

Hint: Height counts edges, not nodes or leaves [OK]

Common Mistakes:

• Confusing height with total nodes
• Counting nodes instead of edges
• Thinking height is number of leaves

2. Which of the following C# method signatures correctly defines a recursive function to find the height of a binary tree node named root?

easy

A. public int Height(Node root, int height)

B. public void Height(Node root)

C. public int Height()

D. public int Height(Node root)

Solution

1. Step 1: Identify correct return type and parameters

   The height function must return an integer representing height, so return type is int. It needs the root node as input, so parameter is Node root.

2. Step 2: Check options for matching signature

   public int Height(Node root) matches: returns int and takes Node root. public void Height(Node root) returns void (wrong), C has no parameters (wrong), D has extra parameter not needed for basic height.

3. Final Answer:

   public int Height(Node root) -> Option D

4. Quick Check:

   Return int and take root node parameter [OK]

Hint: Height returns int and takes root node as parameter [OK]

Common Mistakes:

• Using void return type
• Missing root parameter
• Adding unnecessary parameters

3. What is the output of the following C# code snippet that calculates the height of a binary tree?

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

int Height(Node root) {
  if (root == null) return -1;
  int leftHeight = Height(root.left);
  int rightHeight = Height(root.right);
  return Math.Max(leftHeight, rightHeight) + 1;
}

// Tree:
//     1
//    / \
//   2   3
//  /
// 4

Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);

Console.WriteLine(Height(root));

medium

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Understand the height calculation logic

   Height returns -1 for null nodes. For leaf nodes, height = 0. Height is max of left and right subtree heights plus 1.

2. Step 2: Calculate height for given tree

   Node 4: left and right null, height = 0.
   Node 2: left height 0 (node 4), right null (-1), max=0 +1=1.
   Node 3: leaf, height=0.
   Root 1: left height 1, right height 0, max=1 +1=2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Height of root = 2 edges [OK]

Hint: Height counts edges; leaf node height is 0 [OK]

Common Mistakes:

• Counting nodes instead of edges
• Returning 0 for null instead of -1
• Miscomputing max height

4. Identify the error in this C# method to find the height of a binary tree and select the fix:

int Height(Node root) {
  if (root == null) return 0;
  int leftHeight = Height(root.left);
  int rightHeight = Height(root.right);
  return Math.Max(leftHeight, rightHeight);
}

medium

A. Change base case return from 0 to -1

B. Add +1 to the return statement after Math.Max

C. Remove recursive calls to left and right

D. Change Math.Max to Math.Min

Solution

1. Step 1: Analyze base case and return statement

   Base case returns 0 for null, which means height of empty tree is 0. The recursive calls get left and right heights correctly.

2. Step 2: Check final return calculation

   Height should be max of left and right heights plus 1 for current node. The code misses +1, so height is underestimated.

3. Final Answer:

   Add +1 to the return statement after Math.Max -> Option B

4. Quick Check:

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

Hint: Add +1 after max to count current node [OK]

Common Mistakes:

• Forgetting +1 in return
• Changing base case incorrectly
• Using min 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 return the sum of all node values at the maximum height level. Which approach correctly solves this problem?

hard

A. First find height, then traverse tree again to sum nodes at that height

B. Sum all nodes during height calculation recursively

C. Return height multiplied by root node value

D. Sum all leaf nodes regardless of height

Solution

1. Step 1: Understand problem requirements

   We need the height of the tree and sum of nodes at that height level (deepest level).

2. Step 2: Choose correct approach

   First find height, then traverse tree again to sum nodes at that height: Find height first, then traverse again to sum nodes at that level. This separates concerns and is clear.
   Sum all nodes during height calculation recursively tries to sum during height calculation, but height is computed bottom-up and summing nodes at max height requires separate traversal.
   Return height multiplied by root node value and D do not meet problem requirements.

3. Final Answer:

   First find height, then traverse tree again to sum nodes at that height -> Option A

4. Quick Check:

   Two-pass approach: height then sum at height [OK]

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

Common Mistakes:

• Trying to sum nodes during height recursion
• Multiplying height by root value
• Summing all leaf nodes ignoring height