Balanced Binary Tree

Concept

A Binary Tree achieves its magical $O(\log N)$ speed because every time you make a decision (Go Left or Go Right), you mathematically eliminate half the remaining nodes.

However, if the tree is unbalanced (e.g., the left branch goes down 100 levels, but the right branch is empty), you don’t eliminate half the nodes. The tree degrades into a Linked List, and your speed plummets to $O(N)$.

A Balanced Binary Tree (or Height-Balanced Tree) is a tree where the depth of the two subtrees of every single node never differs by more than 1.

Check if a Tree is Balanced

Problem: Given a binary tree, determine if it is height-balanced. (LeetCode 110).

To determine if a tree is balanced, we must calculate the absolute Height of the Left branch, and the absolute Height of the Right branch. If Math.abs(leftHeight - rightHeight) > 1, it is unbalanced!

The Naive Approach ($O(N^2)$):
We create a getHeight() helper function. We run getHeight(root.left) and getHeight(root.right). If they are balanced, we then recursively call our function on the left and right children to check them.
This is $O(N^2)$ because we are recalculating the heights of the deepest nodes over and over again for every parent check.

The Optimal Approach ($O(N)$): Bottom-Up Post-Order
Instead of top-down, we go Bottom-Up using Post-order traversal.
We ask the deepest leaves for their height (1). They pass it up.
The Parent receives the heights from its Left and Right children. It instantly compares them. If they are unbalanced, the Parent throws a massive error signal (e.g., returning -1) that bubbles all the way up to the Root to instantly fail the entire tree. If it is balanced, the Parent adds 1 to the max height and passes it up to its own parent.

Implementation

function isBalanced(root: TreeNode | null): boolean {
    // If the helper function returns -1, it means a deep branch was unbalanced
    return checkHeight(root) !== -1;
}

function checkHeight(node: TreeNode | null): number {
    // Base Case: An empty node has a height of 0
    if (node === null) return 0;

    // 1. Ask the Left child for its height
    const leftHeight = checkHeight(node.left);
    // If the left child threw the -1 error, instantly bubble it up!
    if (leftHeight === -1) return -1;

    // 2. Ask the Right child for its height
    const rightHeight = checkHeight(node.right);
    // If the right child threw the -1 error, instantly bubble it up!
    if (rightHeight === -1) return -1;

    // 3. Compare the two heights. Are they unbalanced?
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1; // Throw the error signal!
    }

    // 4. They are balanced! Calculate my own height and pass it UP.
    return Math.max(leftHeight, rightHeight) + 1;
}

Convert Sorted Array to Balanced BST

Problem: Given an integer array sorted in ascending order, convert it to a height-balanced BST. (LeetCode 108).

If the array is [1, 2, 3, 4, 5], and we just blindly insert them one by one, we get a degenerate right-leaning straight line.
How do we mathematically force it to be balanced?

The Trick: The middle element of a sorted array is always the mathematically perfect Root! Everything to its left belongs in the Left branch, and everything to its right belongs in the Right branch.
This is a recursive divide-and-conquer algorithm.

function sortedArrayToBST(nums: number[]): TreeNode | null {
    function constructTree(left: number, right: number): TreeNode | null {
        if (left > right) return null;

        // Find the exact middle index
        const mid = Math.floor((left + right) / 2);

        // The middle number becomes the Root
        const node = new TreeNode(nums[mid]);

        // Recursively build the left branch using the left half of the array
        node.left = constructTree(left, mid - 1);
        
        // Recursively build the right branch using the right half of the array
        node.right = constructTree(mid + 1, right);

        return node;
    }

    return constructTree(0, nums.length - 1);
}

Interview Questions

Q: A tree is perfectly balanced, but it is not a Binary Search Tree (the numbers are in random order). Can we still search it in $O(\log N)$ time?
A: No. A balanced tree guarantees that the physical height of the tree is minimal ($O(\log N)$). However, if the data is unsorted (not a BST), you cannot make the mathematical decision to “Go Left or Go Right.” You are forced to execute a full DFS/BFS to check every single node until you find your target. Searching an unsorted tree, balanced or not, always takes $O(N)$ time.

Q: What is an AVL Tree?
A: An AVL Tree is the original “Self-Balancing” Binary Search Tree. It enforces the exact same rule we just coded: the height of the two child subtrees of any node differ by at most one. Every time a new node is inserted into an AVL Tree, it dynamically updates its height. If the math detects an imbalance, it triggers an instant “Tree Rotation” (swapping the parent and child pointers) to physically yank the deep branch upwards, perfectly restoring the balance.