Find the maximun depth or height of a binary tree

Problem:

Given a binary tree, find the maximun depth or height of a binary tree. The height of the tree is the number of vertices in the tree from the root to the deepest node.

Algorithm:

1. If the tree is empty, return 0 (indicating no height).
2. Traverse the left and right subtrees, recursively calculating the height of each.
   1. Recursively calculate the height of the left subtree.
   2. Recursively calculate the height of the right subtree.
3. Determine the maximum height between the left and right subtrees, and add 1 to account for the current node’s height.

This approach calculates the height by recursively determining the heights of the left and right subtrees and returning the greater of the two, plus one for the current node.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm works.

function findMaxDepth(root) {
    if (root === null) return 0;

    let lDepth = findMaxDepth(root.left);
    let rDepth = findMaxDepth(root.right);

    return Math.max(lDepth, rDepth) + 1;
}

const nodes = [1, 2, 3, 4, 5, null, null, null, null, 10];
const root = buildTree(nodes);

findMaxDepth(root); // 4
                                        

class TreeNode {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function buildTree(nodes, index, size) {
    if (index < size) {
        if (nodes[index] === null) {
            return null;
        }

        let root = new TreeNode(nodes[index]);
        root.left = buildTree(nodes, 2 * index + 1, size);
        root.right = buildTree(nodes, 2 * index + 2, size);

        return root;
    }

    return null;
}