Find the minimun depth of a binary tree

Binary Trees

JavaScript

Problem:

Given a binary tree, find the minimun depth of the tree. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Algorithm:

Traverse the binary tree and perform the following operations
1. If the node is a leaf (both left and right children are null), return a depth as 1.
2. If the node is not a leaf and one of the subtrees is null, recursively traverse the other subtree to find its minimum depth.
3. If both subtrees are present, recursively find the minimum depth between the two subtrees.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm works.

Result

Code

Input:

Please enter the Tree nodes:

Output:

solution.js

binary-tree.js

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

    // If it is a leaf node, then the depth is 1
    if (root.left === null && root.right === null) {
        return 1;
    }

    // If left subtree is null, find the minimum depth of the right subtree
    if (root.left === null) {
        return findMinDepth(root.right) + 1;
    }

    // If right subtree is null, find the minimum depth of the left subtree
    if (root.right === null) {
        return findMinDepth(root.left) + 1;
    }

    // If both subtrees are present, then find the minimum of the two
    return Math.min(findMinDepth(root.left), findMinDepth(root.right)) + 1;
}

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

findMinDepth(root); // 2

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;
}