3
\$\begingroup\$

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);
}
}
\$\endgroup\$
2
  • \$\begingroup\$ Just to add, my intention is to do it without recursion. \$\endgroup\$
    – Stifler
    Dec 11, 2014 at 8:47
  • \$\begingroup\$ Are you sure? Because the most efficient way is to use recursion. \$\endgroup\$ Dec 25, 2014 at 1:03

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$

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.