Check if Binary Tree is Balanced in DSA Typescript - Build from Scratch

Check if Binary Tree is Balanced

📖 Scenario: You are working on a program that manages a binary tree structure. A balanced binary tree is one where the difference in height between the left and right subtrees of every node is at most 1. This helps keep operations efficient.Imagine you want to check if your tree is balanced to ensure fast searching and insertion.

🎯 Goal: Build a TypeScript program that creates a binary tree, sets up a helper function to check balance, implements the logic to verify if the tree is balanced, and finally prints the result.

📋 What You'll Learn

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

Create a sample binary tree with exact nodes and structure

Create a helper function called checkHeight that returns the height of a subtree or -1 if unbalanced

Create a function called isBalanced that uses checkHeight to determine if the tree is balanced

Print true or false depending on whether the tree is balanced

💡 Why This Matters

🌍 Real World

Balanced binary trees are used in databases and file systems to keep data organized for fast searching and updating.

💼 Career

Understanding tree balance is important for software engineers working on performance-critical applications and data structure optimization.

1

Create the Binary Tree Structure

Create a class called TreeNode with a constructor that takes a number val and initializes left and right as null. Then create a binary tree with root node value 1, left child 2, and right child 3. The left child 2 should have a left child 4 and right child 5. The right child 3 should have no children.

DSA Typescript

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

Hint

Start by defining the TreeNode class with the required properties. Then create the nodes exactly as described and link them.

2

Create the Helper Function to Check Height

Create a function called checkHeight that takes a TreeNode | null parameter called node. It should return -1 if the subtree is unbalanced. Otherwise, it returns the height of the subtree. Use recursion to get the left and right subtree heights, and if their difference is more than 1, return -1.

DSA Typescript

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

    constructor(val: number) {
        this.val = val;
        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 checkHeight function below
// Your code here

Hint

Use recursion to get heights of left and right subtrees. Return -1 if unbalanced at any point.

3

Create the Function to Check if Tree is Balanced

Create a function called isBalanced that takes a TreeNode | null parameter called root. It should return true if the tree is balanced and false otherwise. Use the checkHeight function inside it and check if the result is not -1.

DSA Typescript

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

    constructor(val: number) {
        this.val = val;
        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 checkHeight(node: TreeNode | null): number {
    if (node === null) {
        return 0;
    }
    const leftHeight = checkHeight(node.left);
    if (leftHeight === -1) return -1;
    const rightHeight = checkHeight(node.right);
    if (rightHeight === -1) return -1;
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }
    return Math.max(leftHeight, rightHeight) + 1;
}

// Create isBalanced function below
// Your code here

Hint

Use the checkHeight function and return true if it does not return -1.

4

Print if the Tree is Balanced

Write a console.log statement to print the result of calling isBalanced with the root node.

DSA Typescript

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

    constructor(val: number) {
        this.val = val;
        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 checkHeight(node: TreeNode | null): number {
    if (node === null) {
        return 0;
    }
    const leftHeight = checkHeight(node.left);
    if (leftHeight === -1) return -1;
    const rightHeight = checkHeight(node.right);
    if (rightHeight === -1) return -1;
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }
    return Math.max(leftHeight, rightHeight) + 1;
}

function isBalanced(root: TreeNode | null): boolean {
    return checkHeight(root) !== -1;
}

// Print the result below
// Your code here

Hint

Call isBalanced(root) and print the result using console.log.