Height of Binary Tree in DSA Javascript - 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

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

Execution Sample

DSA Javascript

function height(node) {
  if (node === null) return 0;
  let leftHeight = height(node.left);
  let 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.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Computed	Tree State
1	Start at root	1	-	-	-	1 / \ 2 3 / \ 4 5
2	Go left	2	-	-	-	Same as above
3	Go left	4	-	-	-	Same as above
4	Check left child	null	-	-	0	Leaf reached
5	Check right child	null	-	-	0	Leaf reached
6	Compute height	4	0	0	1	Node 4 height = 1
7	Go right	5	-	-	-	Node 5 leaf
8	Check left child	null	-	-	0	Leaf reached
9	Check right child	null	-	-	0	Leaf reached
10	Compute height	5	0	0	1	Node 5 height = 1
11	Compute height	2	1	1	2	Node 2 height = 2
12	Go right	3	-	-	-	Node 3 leaf
13	Check left child	null	-	-	0	Leaf reached
14	Check right child	null	-	-	0	Leaf reached
15	Compute height	3	0	0	1	Node 3 height = 1
16	Compute height	1	2	1	3	Root node height = 3

💡 All nodes visited, height computed from bottom up

Variable Tracker

Variable	Start	After Step 6	After Step 10	After Step 11	After Step 15	After Step 16
node	1 (root)	4 (left leaf)	5 (right leaf of 2)	2 (left child of root)	3 (right child of root)	1 (root)
leftHeight	-	0	0	1	0	2
rightHeight	-	0	0	1	0	1
height	-	1	1	2	1	3

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Returning 0 for null nodes means leaf nodes have height 1 (0 + 1). This is shown in steps 4, 5, 8, 9, 13, and 14 where null children return 0.

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

Adding 1 accounts for the current node's level. Steps 6, 10, 11, 15, and 16 show height computed as max(leftHeight, rightHeight) + 1.

How does recursion ensure all nodes are visited?

The function calls itself on left and right children until null is reached (leaf), ensuring bottom-up height calculation as seen in the step sequence.

Visual Quiz - 3 Questions

Look at the execution table, what is the height computed at step 11 for node 2?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Height Computed' column at step 11 in the execution table.

At which step does the function 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 computed.

If the left subtree of node 2 was taller by 1, how would the height at root (step 16) change?

A It would remain 3

B It would become 4

C It would become 2

D It would become 5

💡 Hint

Height at root is max(leftHeight, rightHeight) + 1; increasing leftHeight by 1 increases root height by 1.

Concept Snapshot

Height of Binary Tree:
- Base case: null node height = 0
- Recursively find left and right subtree heights
- Height = max(leftHeight, rightHeight) + 1
- Returns height of tree from bottom up
- Used to measure tree depth

Full Transcript

The height of a binary tree is found by starting at the root and recursively checking the height of left and right children. If a node is null, it returns 0, meaning leaf nodes have height 1. For each node, the height is the maximum height of its left and right subtrees plus one for the current node. This process continues until all nodes are visited and the height of the root node is computed. The execution table shows each step visiting nodes, checking children, and computing heights. The variable tracker follows the node visited and height values at key steps. Key moments clarify why null returns 0 and why we add 1 after max. The visual quiz tests understanding of height values at specific steps and how changes affect the root height.