Height of Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Height of Binary Tree

Start at root node

↓

Is node null?

Yes→Return 0

No↓

Find height of left subtree

↓

Find height of right subtree

↓

Height = max(left, right) + 1

↓

Return height

We start at the root and recursively find the height of left and right subtrees. The height of the node is the maximum of these two heights plus one.

Execution Sample

DSA Typescript

function height(node: TreeNode | null): number {
  if (node === null) return 0;
  const leftHeight = height(node.left);
  const rightHeight = height(node.right);
  return Math.max(leftHeight, rightHeight) + 1;
}

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

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Computed	Tree State
1	Start at root	A	-	-	-	A / \ B C / / \ D E F
2	Go left	B	-	-	-	B / D
3	Go left	D	-	-	-	D (leaf)
4	Left child null	null	0	-	-	-
5	Right child null	null	-	0	-	-
6	Compute height at D	D	0	0	1	D (height=1)
7	Right child null of B	null	-	0	-	-
8	Compute height at B	B	1	0	2	B (height=2)
9	Go right	C	-	-	-	C / \ E F
10	Go left	E	-	-	-	E (leaf)
11	Left child null	null	0	-	-	-
12	Right child null	null	-	0	-	-
13	Compute height at E	E	0	0	1	E (height=1)
14	Go right	F	-	-	-	F (leaf)
15	Left child null	null	0	-	-	-
16	Right child null	null	-	0	-	-
17	Compute height at F	F	0	0	1	F (height=1)
18	Compute height at C	C	1	1	2	C (height=2)
19	Compute height at A	A	2	2	3	A (height=3)
20	Return final height	A	2	2	3	Tree height = 3

💡 All nodes visited, heights computed bottom-up, final height returned at root.

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 13	After Step 17	After Step 18	Final
node	A	D	B	E	F	C	A
leftHeight	-	0	1	0	0	1	2
rightHeight	-	0	0	0	0	1	2
height	-	1	2	1	1	2	3

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Returning 0 for a null node means the height of an empty subtree is zero, as shown in steps 4, 5, 11, 12, 15, and 16 in the execution_table.

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

Adding 1 accounts for the current node's level, as seen in steps 6, 8, 13, 17, 18, and 19 where height is max(leftHeight, rightHeight) + 1.

How does the recursion ensure all nodes are visited?

The recursion visits left and right children before computing height at the current node, demonstrated by the bottom-up order in the execution_table from leaves (D, E, F) to root (A).

Visual Quiz - 3 Questions

Look at the execution_table, what is the height computed at node B (step 8)?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Height Computed' column at step 8 in the execution_table.

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

A Step 11

B Step 17

C Step 13

D Step 6

💡 Hint

Look for node E and height 1 in the execution_table rows.

If node F had a left child, how would the final height of the tree change?

A It would increase by 1

B It would stay the same

C It would decrease

D It would become 0

💡 Hint

Consider how adding a child increases subtree height, affecting the max height at ancestors.

Concept Snapshot

Height of Binary Tree:
- Height is max height of left and right subtree + 1
- Null node height = 0
- Use recursion to find left and right heights
- Return max(leftHeight, rightHeight) + 1
- Base case: node == null returns 0

Full Transcript

The height of a binary tree is found by starting at the root and recursively finding the height of its left and right subtrees. If a node is null, the height is zero. For each node, the height is the maximum of the left and right subtree heights plus one for the current node. This process continues bottom-up until the root's height is computed. The example tree has height 3, as shown by the step-by-step execution where leaf nodes have height 1, their parents have height 2, and the root has height 3.

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 nodes at the root level

Solution

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

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

2. Step 2: Differentiate height from other tree properties

   Number of nodes or leaf nodes are different concepts; height specifically counts edges on the longest path.

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, on longest root-to-leaf path [OK]

Common Mistakes:

• Confusing height with total nodes count
• Counting nodes instead of edges for height
• Thinking height equals number of leaf nodes

2. Which TypeScript function signature correctly defines a recursive function to find the height of a binary tree node?

easy

A. function height(node: TreeNode | null): number

B. function height(node: number): number

C. function height(): void

D. function height(node: TreeNode): string

Solution

1. Step 1: Identify the correct parameter type for a tree node

   The function must accept a node or null (for empty subtree), so type is TreeNode | null.

2. Step 2: Confirm the return type is number

   The height is a numeric value, so the return type must be number.

3. Final Answer:

   function height(node: TreeNode | null): number -> Option A

4. Quick Check:

   Parameter: TreeNode|null, Return: number [OK]

Hint: Height function needs node or null input and returns number [OK]

Common Mistakes:

• Using wrong parameter type like number instead of node
• Returning void or string instead of number
• Missing null to handle empty subtree

3. What is the height of the following binary tree?

    1
   / \
  2   3
 / 
4  

Consider height as number of edges on longest path from root to leaf.

medium

A. 3

B. 4

C. 1

D. 2

Solution

1. Step 1: Identify all root-to-leaf paths and count edges

   Paths: 1->2->4 has 2 edges, 1->3 has 1 edge.

2. Step 2: Find the longest path edge count

   Longest path is 1->2->4 with 2 edges.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Longest path edges = 2 [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Choosing shorter path length
• Confusing height with tree depth

4. Identify the error in this TypeScript function to find binary tree height:

function height(node: TreeNode | null): number {
  if (!node) return 0;
  return Math.max(height(node.left), height(node.right));
}

medium

A. Returns 0 for null node instead of -1

B. Uses Math.min instead of Math.max

C. Missing +1 to count current node edge

D. Function should return void

Solution

1. Step 1: Analyze base case return value

   Returning 0 for null means empty subtree height is 0, which is acceptable if counting edges from nodes.

2. Step 2: Check recursive return statement

   Function returns max height of children but misses adding 1 for current edge from node to child.

3. Final Answer:

   Missing +1 to count current node edge -> Option C

4. Quick Check:

   Height = max child height + 1 edge [OK]

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

Common Mistakes:

• Forgetting to add 1 for current node edge
• Returning wrong base case value
• Using min instead of max for height

5. Given a binary tree where each node has a value, write a function to find the height of the tree but only counting nodes with even values. What is the height of this tree?

    2
   / \
  3   4
 /   / \
6   5   8

hard

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Identify nodes with even values and their connections

   Even nodes: 2 (root), 4 (right child), 6 (left-left child), 8 (right-right child). Paths counting only even nodes:
• 2 -> 4 -> 8 (edges = 2)
• 2 -> 3 (3 is odd, so path ends at 2)
• 2 -> 3 -> 6 (6 is even but 3 is odd, so path breaks at 3)

2. Step 2: Calculate height counting only edges between even nodes

   Longest path with even nodes is 2 -> 4 -> 8 with 2 edges.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Longest even-valued node path edges = 2 [OK]

Hint: Count edges only between even-valued nodes [OK]

Common Mistakes:

• Counting odd nodes in path
• Counting nodes instead of edges
• Ignoring breaks caused by odd nodes