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

• Stifler: Just to add, my intention is to do it without recursion.
• TheCoffeeCup: Are you sure? Because the most efficient way is to use recursion.

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.