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