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.