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

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;

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() {
int depth = 0;
while (!queue.isEmpty()) {
while ((head = queue.remove()) != null) {
return depth;
}
}
}
}
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;
}

}


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;

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;

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) {
}

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

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