Height of Binary Tree in DSA Javascript

Mental Model

The height of a binary tree is the longest path from the root to any leaf node. It tells us how tall the tree is.

Analogy: Imagine a family tree where the height is the number of generations from the oldest ancestor (root) down to the youngest descendant (leaf).

      1
     / \
    2   3
   / 
  4  

(Height is 3 because the longest path is 1 -> 2 -> 4)

Dry Run Walkthrough

Input: Binary tree: 1 -> 2 -> 4 (left child), 1 -> 3 (right child)

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

Step 1: Start at root node 1, check left subtree height

1 ↑
Left subtree: 2 -> 4
Right subtree: 3

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

Step 2: At node 2, check left subtree height

2 ↑
Left subtree: 4
Right subtree: null

Why: Continue down left subtree to find longest path

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

4 ↑
Left subtree: null
Right subtree: null

Why: Leaf node height is 1

Step 4: Back to node 2, left height is 1, right height is 0, so height is 1 + max(1,0) = 2

2 ↑
Height calculated as 2

Why: Height includes current node plus max height of children

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

3 ↑
Left subtree: null
Right subtree: null

Why: Leaf node height is 1

Step 6: Back to root 1, left height is 2, right height is 1, so height is 1 + max(2,1) = 3

1 ↑
Height calculated as 3

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

Result:

Height of tree = 3

Annotated Code

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function heightOfBinaryTree(root) {
  if (root === null) return 0; // base case: empty tree has height 0
  const leftHeight = heightOfBinaryTree(root.left); // find left subtree height
  const rightHeight = heightOfBinaryTree(root.right); // find right subtree height
  return 1 + Math.max(leftHeight, rightHeight); // height is 1 + max of subtrees
}

// Driver code
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);

const height = heightOfBinaryTree(root);
console.log("Height of tree = " + height);

if (root === null) return 0;

base case: empty subtree has height 0

const leftHeight = heightOfBinaryTree(root.left);

recursively find height of left subtree

const rightHeight = heightOfBinaryTree(root.right);

recursively find height of right subtree

return 1 + Math.max(leftHeight, rightHeight);

height is current node plus max height of children

Output

Height of tree = 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: Iterative methods exist but recursion is simpler and intuitive for tree height calculation

Edge Cases

Empty tree (root is null)

Returns height 0 as there are no nodes

DSA Javascript

if (root === null) return 0;

Tree with only one node

Returns height 1 because root is also leaf

DSA Javascript

return 1 + Math.max(leftHeight, rightHeight);

Tree with only left or only right children

Correctly calculates height by following the existing subtree

DSA Javascript

const leftHeight = heightOfBinaryTree(root.left);

When to Use This Pattern

When you see a problem asking for the longest path from root to leaf or depth of a tree, reach for the height calculation pattern using recursion.

Common Mistakes

Mistake: Returning 0 for leaf nodes instead of 1
Fix: Return 1 for leaf nodes by adding 1 to max height of children

Mistake: Not handling null root and causing errors
Fix: Add base case to return 0 when root is null

Summary

Calculates the longest path from root to any leaf node in a binary tree.

Use it when you need to know how tall or deep a tree is.

The height is 1 plus the maximum height of its left and right subtrees.