Height of Binary Tree in DSA Typescript - Build from Scratch

Height of Binary Tree

📖 Scenario: You are working with a simple family tree represented as a binary tree. Each person can have up to two children. You want to find out how tall this family tree is, which means finding the longest path from the oldest ancestor (root) down to the youngest descendant (leaf).

🎯 Goal: Build a TypeScript program that creates a binary tree, sets up a helper function to calculate the height of the tree, and then prints the height.

📋 What You'll Learn

Create a binary tree node class called TreeNode with value, left, and right properties

Create a binary tree with exactly 5 nodes using TreeNode instances

Write a recursive function called getHeight that calculates the height of the binary tree

Print the height of the binary tree

💡 Why This Matters

🌍 Real World

Binary trees are used in many real-world applications like organizing family trees, file systems, and decision-making processes.

💼 Career

Understanding tree height is important for jobs involving data structures, algorithms, and software engineering, especially in optimizing search and traversal operations.

1

Create the Binary Tree Nodes

Create a class called TreeNode with a constructor that takes a value of type number. The class should have public properties value, left, and right where left and right are either TreeNode or null. Then create a binary tree with 5 nodes exactly as follows:
root with value 1,
root's left child with value 2,
root's right child with value 3,
left child's left child with value 4,
left child's right child with value 5.

DSA Typescript

// Define TreeNode class and create the binary tree nodes
// Your code here

Hint

Start by defining the TreeNode class with the required properties and constructor. Then create the root node and assign its children as described.

2

Set Up the Height Calculation Function

Create a function called getHeight that takes a parameter node of type TreeNode | null and returns a number. Initialize the base case to return 0 if node is null.

DSA Typescript

class TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// Create getHeight function with base case
// Your code here

Hint

Write a function that returns 0 when the input node is null. This is the base case for the height calculation.

3

Complete the Height Calculation Logic

Inside the getHeight function, recursively call getHeight on node.left and node.right. Return 1 + Math.max(leftHeight, rightHeight) where leftHeight and rightHeight are the heights of the left and right subtrees respectively.

DSA Typescript

class TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

function getHeight(node: TreeNode | null): number {
    if (node === null) {
        return 0;
    }
    // Calculate leftHeight and rightHeight
    // Return 1 + max of leftHeight and rightHeight
    // Your code here
}

Hint

Use recursion to find the height of left and right children, then add 1 for the current node.

4

Print the Height of the Binary Tree

Use console.log to print the height of the binary tree by calling getHeight(root).

DSA Typescript

class TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

function getHeight(node: TreeNode | null): number {
    if (node === null) {
        return 0;
    }
    const leftHeight = getHeight(node.left);
    const rightHeight = getHeight(node.right);
    return 1 + Math.max(leftHeight, rightHeight);
}

// Print the height of the tree
// Your code here

Hint

Call getHeight with root and print the result using console.log.

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