Height of Binary Tree in DSA C# - Execution Trace

Concept Flow - Height of Binary Tree

Start at root node

↓

Is node null?

Yes→Return 0

No↓

Recursively find height of left subtree

↓

Recursively find height of right subtree

↓

Calculate max(leftHeight, rightHeight) + 1

↓

Return height

Start from the root, recursively find the height of left and right subtrees, then return the larger height plus one.

Execution Sample

DSA C#

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 checking left and right subtree heights.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Returned	Tree State
1	Visit root	1	-	-	-	1
2	Visit left child	2	-	-	-	1 -> 2
3	Visit left child of 2	4	-	-	-	1 -> 2 -> 4
4	Left child of 4 is null	null	0	-	-	1 -> 2 -> 4
5	Right child of 4 is null	null	-	0	-	1 -> 2 -> 4
6	Calculate height at node 4	4	0	0	1	1 -> 2 -> 4
7	Visit right child of 2	5	-	-	-	1 -> 2 -> 4,5
8	Left child of 5 is null	null	0	-	-	1 -> 2 -> 4,5
9	Right child of 5 is null	null	-	0	-	1 -> 2 -> 4,5
10	Calculate height at node 5	5	0	0	1	1 -> 2 -> 4,5
11	Calculate height at node 2	2	1	1	2	1 -> 2 -> 4,5
12	Visit right child of root	3	-	-	-	1 -> 2 -> 4,5,3
13	Left child of 3 is null	null	0	-	-	1 -> 2 -> 4,5,3
14	Right child of 3 is null	null	-	0	-	1 -> 2 -> 4,5,3
15	Calculate height at node 3	3	0	0	1	1 -> 2 -> 4,5,3
16	Calculate height at root	1	2	1	3	1 -> 2 -> 4,5,3
17	Return final height	root	-	-	3	1 -> 2 -> 4,5,3

💡 All nodes visited, recursion unwound, final height returned as 3

Variable Tracker

Variable	Start	After Step 6	After Step 10	After Step 11	After Step 15	After Step 16	Final
node	root(1)	4	5	2	3	1	null
leftHeight	-	0	0	1	0	2	-
rightHeight	-	0	0	1	0	1	-
heightReturned	-	1	1	2	1	3	3

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Because a null node means no tree exists there, so its height is 0. This is shown in steps 4 and 5 where left and right children are null and return 0.

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

Adding 1 counts the current node itself. For example, at step 16, max of leftHeight=2 and rightHeight=1 is 2, plus 1 gives height 3 including the root.

How does recursion help find the height?

Recursion breaks the problem into smaller parts: find height of left and right subtrees first (steps 2-15), then combine results at each node (steps 6,10,11,15,16).

Visual Quiz - 3 Questions

Look at the execution table, what is the height returned at step 11 (node 2)?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Height Returned' column at step 11 in the execution_table.

At which step does the recursion return height 1 for node 5?

A Step 10

B Step 6

C Step 15

D Step 16

💡 Hint

Look for node 5 in the 'Node Visited' column and check the 'Height Returned' at that step.

If the left child of node 2 was null, what would be the height returned at step 11?

A 3

B 1

C 2

D 0

💡 Hint

If left child null, leftHeight=0, rightHeight=1 (from node 5), max(0,1)+1=2.

Concept Snapshot

Height of Binary Tree:
- Height is max depth from root to leaf.
- Base case: null node height = 0.
- Recursively find left and right subtree heights.
- Height = max(leftHeight, rightHeight) + 1.
- Returns total nodes count along longest path.

Full Transcript

To find the height of a binary tree, start at the root node. If the node is null, return 0 because there is no tree there. Otherwise, recursively find the height of the left subtree and the right subtree. Then take the maximum of these two heights and add 1 to count the current node. This process continues until all nodes are visited and the recursion unwinds, returning the height of the entire tree. For example, in the traced tree, the height returned is 3, meaning the longest path from root to leaf has 3 nodes.

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