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.

Practice

1. What does the height of a binary tree represent?

easy

A. The number of children of the root node

B. The total number of nodes in the tree

C. The number of leaf nodes in the tree

D. The number of edges on the longest path from root to a leaf

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 D

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 of the following is the correct base case to find the height of a binary tree recursively in JavaScript?

easy

A. if (node === null) return -1;

B. if (node === null) return 0;

C. if (node === undefined) return 1;

D. if (node === undefined) return 0;

Solution

1. Step 1: Understand the base case for empty subtree

   When the node is null (no node), height is defined as -1 to count edges properly.

2. Step 2: Why -1 instead of 0?

   Returning -1 for null ensures leaf nodes have height 0 (0 edges below them), matching edge count definition.

3. Final Answer:

   if (node === null) return -1; -> Option A

4. Quick Check:

   Empty node height = -1 for correct edge count [OK]

Hint: Use -1 for null node to count edges correctly [OK]

Common Mistakes:

• Returning 0 for null node causes off-by-one height
• Checking undefined instead of null for nodes
• Confusing node absence with leaf node

3. What is the output of the following code snippet?

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

function height(node) {
  if (node === null) return -1;
  return 1 + Math.max(height(node.left), height(node.right));
}

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(3);
root.left.left.left = new Node(1);

console.log(height(root));

medium

A. 5

B. 3

C. 4

D. 2

Solution

1. Step 1: Trace the tree structure and count edges

   The longest path is from root (10) to left-left-left (1): edges are 10->5, 5->3, 3->1, total 3 edges.

2. Step 2: Calculate height using the function logic

   Function returns 1 + max height of children. For leaf node (1), height = 0. So total height = 3 edges means function returns 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Longest path edges = 3 [OK]

Hint: Count edges on longest path, not nodes [OK]

Common Mistakes:

• Counting nodes instead of edges for height
• Misreading tree structure and missing deepest node
• Confusing return value for leaf node height

4. Find the error in this height function and select the correct fix:

function height(node) {
  if (node === null) return 0;
  return Math.max(height(node.left), height(node.right));
}

medium

A. Change base case to return -1 instead of 0

B. Return sum instead of max of left and right heights

C. Add +1 before Math.max to count current node

D. No error, function is correct

Solution

1. Step 1: Analyze the base case and recursive return

   Base case returns 0 for null, which is acceptable if counting nodes, but function misses adding 1 for current node.

2. Step 2: Identify missing increment for current node

   Function returns max height of children but does not add 1 for current node, so height is underestimated by 1.

3. Final Answer:

   Add +1 before Math.max to count current node -> Option C

4. Quick Check:

   Height = 1 + max(child heights) [OK]

Hint: Add +1 to include current node in height [OK]

Common Mistakes:

• Forgetting to add 1 for current node
• Changing base case unnecessarily
• Returning sum instead of max height

5. Given a binary tree where some nodes have only one child, how does the height calculation change if you want to count the number of nodes on the longest path instead of edges? Choose the correct modification to the recursive height function.

function height(node) {
  if (node === null) return ?;
  return ? + Math.max(height(node.left), height(node.right));
}

hard

A. Return 0 for null; add 1 before Math.max to count nodes

B. Return -1 for null; add 1 before Math.max to count nodes

C. Return 1 for null; add 0 before Math.max to count nodes

D. Return 0 for null; add 0 before Math.max to count nodes

Solution

1. Step 1: Understand difference between counting edges and nodes

   Counting nodes means height of empty tree is 0, and each node adds 1 to path length.

2. Step 2: Adjust base case and recursive addition accordingly

   Return 0 for null node (no nodes), and add 1 for current node to count nodes on path.

3. Final Answer:

   Return 0 for null; add 1 before Math.max to count nodes -> Option A

4. Quick Check:

   Height counts nodes: base=0, add 1 per node [OK]

Hint: Use 0 base and add 1 to count nodes, not edges [OK]

Common Mistakes:

• Using -1 base for node count causes off-by-one
• Not adding 1 for current node
• Confusing edges count with nodes count