patternjavaMinor

Given a binary tree, compute the min depth of a leaf node

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

depththecomputenodeminleafbinarygiventree

Problem

Here is the source of the question. They don't require a tree to be a BST, but my tree is. The algorithm would be the same for a simple binary tree.

And there are two implementations:

A recursive one

A BFS-based one

They also ask which implementation is better. I think the BFS-based one is because in case of an unbalanced tree we compute the min. depth as soon as we run into a leaf. And using the recursive approach, we have to traverse the whole tree anyway.

For example:

The BFS-based algorithm traverses the first two levels (3 nodes) and returns 1.

Please let me know if the methods don't work for any input data.

GitHub

Node

package algo.mindepth;

    public class Node {

        int mData;
        Node mLeft;
        Node mRight;

        public Node(int data) {
            mData = data;
        }

        @Override
        public String toString() {
            return Integer.toString(mData);
        }
    }

Tree

```
package algo.mindepth;

import java.util.LinkedList;

public class Tree {

private final Node mRoot;

public Tree(int data) {
mRoot = new Node(data);
}

public void insert(int data) {
Node root = mRoot;
while (((root.mData > data) ? (root.mLeft) : (root.mRight)) != null) {
root = ((root.mData > data) ? (root.mLeft) : (root.mRight));
}
if (root.mData > data) {
root.mLeft = new Node(data);
} else {
root.mRight = new Node(data);
}
}

public int getMinDepth() {
return getMinDepth(mRoot);
}

private int getMinDepth(Node root) {
if (root.mLeft == null && root.mRight == null) {
return 0;
}

int minLeft = Integer.MAX_VALUE;
if (root.mLeft != null) {
minLeft = getMinDepth(root.mLeft);
}

int minRight = Integer.MAX_VALUE;
if (root.mRight !

Solution

See the code below. I have added the comments directly in the code snippet wherever I have something to say.

package algo.mindepth;

import java.util.Deque;
import java.util.LinkedList;

public class Tree {

    // 'static' here ensures that each 'Node' does not cache a reference to 
    // 'Tree'.
    private static class Node {

        int  datum;
        Node left;
        Node right;

        Node(final int datum) {
            this.datum = datum;
        }
    }

    // Keeping the root final is not a good idea: 
    // You have to deal somehow with zero size trees.
    private /*final*/ Node root;

    // It is odd to have a constructor which accepts only one single element.
    // Accept none or arbitrary amount of initializers.
    public Tree(final int... data) {
        for (final int datum : data) {
            insert(datum);
        }
    }

    // This is a matter of taste, but I prefer to use a singular form, which
    // for word "data" is "datum". The 'final' keyword would not hurt either.
    // This way you ensure that you cannot involuntarily assign to
    // variables that should not be assigned to.
    public void insert(final int datum) {
        if (root == null) {
            root = new Node(datum);
            return;
        }

        Node parent = null;
        Node current = root;

        while (current != null) {
            parent = current;
            current = datum  queue = new LinkedList<>();
        int depth = 0;

        Node endOfLevel = root;
        queue.add(root);

        for (;;) {
            final Node current = queue.poll();

            // Reached the closest leaf.
            if (current.left == null && current.right == null) {
                return depth;
            }

            // Expand the left node.
            if (current.left != null) {
                queue.addLast(current.left);
            }

            // Expand the right node.
            if (current.right != null) {
                queue.addLast(current.right);
            }

            // If 'current' has child nodes, they were added above,
            // the 'queue' cannot be empty. Otherwise, we would have reached
            // a leaf node, and thus terminate.
            if (current == endOfLevel) {
                // We just finished a tree level. 
                // Choose the new level terminator and increment depth.
                endOfLevel = queue.getLast();
                ++depth;
            }
        }
    }
}

There is a couple of places where you can do more clean code, yet your overall approach is good.

Code Snippets

package algo.mindepth;

import java.util.Deque;
import java.util.LinkedList;

public class Tree {

    // 'static' here ensures that each 'Node' does not cache a reference to 
    // 'Tree'.
    private static class Node {

        int  datum;
        Node left;
        Node right;

        Node(final int datum) {
            this.datum = datum;
        }
    }

    // Keeping the root final is not a good idea: 
    // You have to deal somehow with zero size trees.
    private /*final*/ Node root;

    // It is odd to have a constructor which accepts only one single element.
    // Accept none or arbitrary amount of initializers.
    public Tree(final int... data) {
        for (final int datum : data) {
            insert(datum);
        }
    }

    // This is a matter of taste, but I prefer to use a singular form, which
    // for word "data" is "datum". The 'final' keyword would not hurt either.
    // This way you ensure that you cannot involuntarily assign to
    // variables that should not be assigned to.
    public void insert(final int datum) {
        if (root == null) {
            root = new Node(datum);
            return;
        }

        Node parent = null;
        Node current = root;

        while (current != null) {
            parent = current;
            current = datum < current.datum ? 
                              current.left : 
                              current.right;
        }

        if (datum < parent.datum) {
            parent.left = new Node(datum);
        } else {
            parent.right = new Node(datum);
        }
    }

    public int getMinDepth() {
        return getMinDepth(root);
    }

    private int getMinDepth(final Node root) {
        if (root.left == null && root.right == null) {
            return 0;
        }

        int minLeft = Integer.MAX_VALUE;

        if (root.left != null) {
            minLeft = getMinDepth(root.left);
        }

        int minRight = Integer.MAX_VALUE;

        if (root.right != null) {
            minRight = getMinDepth(root.right);
        }

        return Math.min(minLeft, minRight) + 1;
    }

    public int getMinDepthBFS() {
        if (root == null) {
            // Let us define that the depth (height) of an empty tree is -1.
            // 0 is for the tree with only one node.
            return -1;
        }

        final Deque<Node> queue = new LinkedList<>();
        int depth = 0;

        Node endOfLevel = root;
        queue.add(root);

        for (;;) {
            final Node current = queue.poll();

            // Reached the closest leaf.
            if (current.left == null && current.right == null) {
                return depth;
            }

            // Expand the left node.
            if (current.left != null) {
                queue.addLast(current.left);
            }

            // Expand the right node.
            if (current.right != null) {
                queue.addLast(current.right);
            }

            // If '

Context

StackExchange Code Review Q#90250, answer score: 7

Revisions (0)

No revisions yet.