Height of Binary Tree in DSA Typescript

Mental Model

The height of a binary tree is the longest path from the root to any leaf node. We find it by checking the height of left and right subtrees and taking the bigger one plus one.

Analogy: Imagine a family tree where height is how many generations you count from the oldest ancestor down to the youngest descendant in the longest line.

      1
     / \
    2   3
   /   / \
  4   5   6

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2, right child 3; 2 has left child 4; 3 has children 5 and 6

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

Step 1: Start at root node 1, find height of left subtree rooted at 2

At node 1 -> going left to node 2

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

Step 2: At node 2, find height of left subtree rooted at 4

At node 2 -> going left to node 4

Why: Continue down left subtree to find its height

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

Node 4 is leaf -> height = 1

Why: Leaf node height is 1 by definition

Step 4: At node 2, right child is null, height is 0; max height is max(1,0)+1=2

Node 2 height = 2

Why: Height is max of left and right subtree heights plus one for current node

Step 5: At node 1, find height of right subtree rooted at 3

At node 1 -> going right to node 3

Why: Now find height of right subtree to compare

Step 6: At node 3, find height of left subtree rooted at 5

At node 3 -> going left to node 5

Why: Check left child of node 3

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

Node 5 is leaf -> height = 1

Why: Leaf node height is 1

Step 8: At node 3, find height of right subtree rooted at 6

At node 3 -> going right to node 6

Why: Check right child of node 3

Step 9: At node 6, no children, height is 1

Node 6 is leaf -> height = 1

Why: Leaf node height is 1

Step 10: At node 3, max height is max(1,1)+1=2

Node 3 height = 2

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

Step 11: At root node 1, max height is max(2,2)+1=3

Root node 1 height = 3

Why: Height of tree is max height of subtrees plus one for root

Result:

Height = 3

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function heightOfBinaryTree(root: TreeNode | null): number {
  if (root === null) return 0; // base case: empty tree has height 0

  const leftHeight = heightOfBinaryTree(root.left); // find height of left subtree
  const rightHeight = heightOfBinaryTree(root.right); // find height of right subtree

  return Math.max(leftHeight, rightHeight) + 1; // height is max subtree height + 1
}

// Driver code to build the tree from dry run input
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), null),
  new TreeNode(3, new TreeNode(5), new TreeNode(6))
);

const result = heightOfBinaryTree(root);
console.log(result);

if (root === null) return 0; // base case: empty tree has height 0

stop recursion when no node (leaf's child) reached

const leftHeight = heightOfBinaryTree(root.left); // find height of left subtree

recursively find height of left subtree

const rightHeight = heightOfBinaryTree(root.right); // find height of right subtree

recursively find height of right subtree

return Math.max(leftHeight, rightHeight) + 1; // height is max subtree height + 1

combine left and right heights, add one for current node

Output

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 call stack

vs Alternative: Compared to iterative BFS which uses queue and also O(n) time, recursion is simpler but uses call stack space

Edge Cases

Empty tree (root is null)

Returns height 0 immediately

DSA Typescript

if (root === null) return 0; // base case: empty tree has height 0

Single node tree

Returns height 1 as root is also leaf

DSA Typescript

return Math.max(leftHeight, rightHeight) + 1; // height is max subtree height + 1

Unbalanced tree (all nodes on one side)

Height equals number of nodes in longest chain

DSA Typescript

return Math.max(leftHeight, rightHeight) + 1; // height is max subtree height + 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 by recursively checking subtree heights.

Common Mistakes

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

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

The height is the bigger height between left and right subtrees 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 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