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.