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