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.