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.