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

Question

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:

1. A recursive one
2. 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:

          40
         /  \
      12  42
       / \
    11  13
   / \
  9  12
   / \
  8  10

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 != null) {
            minRight = getMinDepth(root.mRight);
        }

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

    public int getMinDepthBfs() {
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(mRoot);
        queue.add(null);
        int depth = 0;
        while (!queue.isEmpty()) {
            Node head = null;
            while ((head = queue.remove()) != null) {
                if (head.mLeft == null && head.mRight == null) {
                    return depth;
                }
                if (head.mLeft != null) {
                    queue.add(head.mLeft);
                }
                if (head.mRight != null) {
                    queue.add(head.mRight);
                }
            }
            queue.add(null);
            depth++;
        }

        return depth;
    }
}

Tests

package algo.mindepth;

import static org.junit.Assert.assertEquals;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

import java.util.Arrays;
import java.util.Collection;

@RunWith(Parameterized.class)
public class MinDepthTest {

    @Parameters
    public static Collection<Object[]> data() {
        return Arrays.asList(new Object[][] {
                { fillSingleLeaf(), 0 },
                { fillTwoLeavesBalanced(), 1 },
                { fillLeftSubtree(), 2 },
                { fillBalancedTwoLevels(), 2 },
                { fillRightSubtree(), 2 },
                { fillLeftPath(), 3 },
                { fillRightPath(), 3 }
        });
    }

    private Tree fInput;

    private int fExpected;

    public MinDepthTest(Tree input, int expected) {
        fInput = input;
        fExpected = expected;
    }

    @Test
    public void testRecursive() {
        assertEquals(fExpected, fInput.getMinDepth());
    }

    @Test
    public void testBfs() {
        assertEquals(fExpected, fInput.getMinDepthBfs());   
    }

    /*
     *          10
     */
    private static Tree fillSingleLeaf() {
        Tree tree = new Tree(10);
        return tree;
    }

    /*
     *          10
     *        /    \
     *       3     13
     */
    private static Tree fillTwoLeavesBalanced() {
        Tree tree = new Tree(10);
        tree.insert(3);
        tree.insert(13);
        return tree;
    }

    /*
     *          10
     *         /
     *        3
     *       / \
     *      2   7
     *     /
     *    1
     */
    private static Tree fillLeftSubtree() {
        Tree tree = new Tree(10);
        tree.insert(3);
        tree.insert(7);
        tree.insert(2);
        tree.insert(1);
        return tree;
    }


    /*
     *      10
     *        \
     *        14
     *        / \
     *       12  16
     */
    private static Tree fillRightSubtree() {
        Tree tree = new Tree(10);
        tree.insert(13);
        tree.insert(14);
        tree.insert(12);
        tree.insert(16);
        return tree;
    }

    /*
     *         10
     *        /  \
     *       7    13
     *      / \   / \
     *     2   9 12  15
     */
    private static Tree fillBalancedTwoLevels() {
        Tree tree = new Tree(10);
        tree.insert(13);
        tree.insert(7);
        tree.insert(2);
        tree.insert(9);
        tree.insert(12);
        tree.insert(15);
        return tree;
    }

    /*
     *          10
     *         /
     *        7
     *       /
     *      2
     *     /
     *    1 
     */
    private static Tree fillLeftPath() {
        Tree tree = new Tree(10);
        tree.insert(7);
        tree.insert(2);
        tree.insert(1);
        return tree;
    }

    /*
     *         10
     *           \
     *            15
     *              \
     *               17
     *                \
     *                 21
     */
    private static Tree fillRightPath() {
        Tree tree = new Tree(10);
        tree.insert(15);
        tree.insert(17);
        tree.insert(21);
        return tree;
    }

}

Answer 1

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 < 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 '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.