6
\$\begingroup\$

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

}
\$\endgroup\$

1 Answer 1

7
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.