Deepest node in tree

Question

I have written two classes, one to represent the tree and a Util class to get the deepest node from the tree. Can you please review the code?

Below is the class for Tree:

package org.vik.ds.tree;

public class BinaryTree<E>{

private E data;
private BinaryTree<E> leftNode;
private BinaryTree<E> rightNode;

public BinaryTree(E data, BinaryTree<E> leftNode, BinaryTree<E> rightNode)
{
    this.data = data;
    this.leftNode = leftNode;
    this.rightNode = rightNode;
}

public E getData()
{
    return data;
}

public void setData(E data)
{
    this.data = data;
}

public BinaryTree<E> getLeftNode()
{
    return leftNode;
}

public void setLeftNode(BinaryTree<E> leftNode)
{
    this.leftNode = leftNode;
}

public BinaryTree<E> getRightNode()
{
    return rightNode;
}

public void setRightNode(BinaryTree<E> rightNode)
{
    this.rightNode = rightNode;
}

public boolean isLeafNode()
{
    return (leftNode == null && rightNode == null);

}

}

Below is algo class, which finds deepest node in tree:

public class DeepestNodeInTree{

public static <T> BinaryTree<T> getDeepestNode(BinaryTree<T> rootNode)
{
    BinaryTree<T> deepestNode = rootNode;
    int maxDeeper = 0;

    Deque<BinaryTree<T>> nodeStack = new LinkedList<BinaryTree<T>>();

    BinaryTree<T> tempNode = rootNode;
    Map<BinaryTree<T>, Boolean> isNodeVisitedMap = new HashMap<>();
    while (tempNode != null)
    {

        if (tempNode.isLeafNode())
        {
            int currentMaxDeeperLen = nodeStack.size() - 1;
            if (currentMaxDeeperLen > maxDeeper)
            {
                deepestNode = tempNode;
                maxDeeper = currentMaxDeeperLen;

            }

            isNodeVisitedMap.put(tempNode, true);
            tempNode = nodeStack.isEmpty() ? nodeStack.pop() : null;
        }
        else
        {

            BinaryTree<T> notVisitedChildNode = getNonVisitedChildNode(tempNode, isNodeVisitedMap);
            if (notVisitedChildNode != null)
            {
                nodeStack.push(tempNode);
                tempNode = notVisitedChildNode;
            }
            else
            {
                isNodeVisitedMap.put(tempNode, true);
                tempNode = nodeStack.isEmpty() ? nodeStack.pop() : null;

            }
        }
    }
    return deepestNode;
}

/**
 * This will get left or right node, if both node is visited it will return
 * null
 * 
 * @param tempNode
 * @param isNodeVisitedMap
 * @return
 */
private static <T> BinaryTree<T> getNonVisitedChildNode(BinaryTree<T> tempNode,
        Map<BinaryTree<T>, Boolean> isNodeVisitedMap)
{
    BinaryTree<T> childNode = tempNode.getLeftNode();

    if (isNodeVisited(isNodeVisitedMap, childNode))
    {
        childNode = isNodeVisited(isNodeVisitedMap, tempNode.getRightNode()) ? null : tempNode.getRightNode();
    }
    return childNode;
}

private static <T> boolean isNodeVisited(Map<BinaryTree<T>, Boolean> isNodeVisitedMap, BinaryTree<T> childNode)
{
    return childNode == null || isNodeVisitedMap.containsKey(childNode);
}
}

Answer 1

Your braces do not follow the Standard Java Conventions. The standard way is:

public BinaryTree(E data, BinaryTree<E> leftNode, BinaryTree<E> rightNode) {
    this.data = data;
    this.leftNode = leftNode;
    this.rightNode = rightNode;
}

Notice the movement of the braces.

You should have a constructor for your BinaryTree that takes no parameters and one that takes only the data:

public BinaryTree() {

}

public BinaryTree(E data) {
    this.data = data;
}

public BinaryTree(E data, BinaryTree<E> leftNode, BinaryTree<E> rightNode) {
    this.data = data;
    this.leftNode = leftNode;
    this.rightNode = rightNode;
}

This way, programmers using it has a choice of being able to give less information, and add it later through the set() methods. Also, this allows them to prevent them from doing stuff like:

BinaryTree<Integer> tree = new BinaryTree<Integer>(null, null, null);

After all, who wants to do that?

I don't see any point in making a separate class for finding the deepest node int the tree. Why not just put it under one class?

There is a better way to do it with recursion:

public BinaryTree<E> getDeepestNode(BinaryTree<E> rootNode) {
    if (rootNode.leftNode.isLeafNode() && rootNode.rightNode.isLeafNode()) {
        return rootNode;
    }
    return getDeepestNode(rootNode.getLeftNode(), 0) > getDeepestNode(
            rootNode.getRightNode(), 0) ? getDeepestNode(rootNode
            .getLeftNode()) : getDeepestNode(rootNode.getRightNode());
}

private int getDeepestNode(BinaryTree<E> rootNode, int depth) {
    if (rootNode.leftNode.isLeafNode() && rootNode.rightNode.isLeafNode()) {
        return depth + 1;
    }
    return getDeepestNode(rootNode, depth + 1);
}

I know you wanted it without recursion, but I only came up with a solution by using recursion. If you really don't want to use recursion, then your code is fine.