Path from the root to a given node in binary tree

Question

Based on the solution provided in this question , I have written non-recursive Java code to find the path form to a given element in a binary tree. This code is working for all the elements except root.

Is this the correct implementation of the algorithm provided? Please check and suggest the required changes for the code to look more elegant.

public void findPathFromRoot(Node rootNode,int key) 
{
 Node temp = rootNode;
 Stack<Node> nodeStack = new Stack<Node>();
 nodeStack.push(rootNode);
 boolean present = true;
 Node topNode = rootNode;
 Node topNodeLeft,topNodeRight;
 while(true)
 {
 //three temp variables for top,left of top,right of top
 topNode = nodeStack.peek();
 topNodeLeft = topNode.lnode;
 topNodeRight = topNode.rnode;
 //if left of top is not null, push to stack. Check if the push values is equla to the required key
 //If it is the require element break
 if(topNodeLeft != null )
 {
 nodeStack.push(topNodeLeft);
 if(topNodeLeft.value == key)
 break;
 }
 //if right of top is not null, push to stack. Check if the push values is equal to the required key
 //If it is the require element break
 else if(topNodeRight != null)
 {
 nodeStack.push(topNodeRight);
 if(topNodeRight.value == key)
 break;
 }
 //If both the childs are null(ie leaf node) , pop the elements in stack, till the top node has some right child.
 else
 { 
 Node lastPoppedNode;
 //pop the elements in stack, till the top node has some right child.
 do{
 lastPoppedNode = nodeStack.pop();
 topNode = nodeStack.peek();
 }while(topNode.rnode==null); 
 //Now the top node would be the node with some right child
 topNodeRight = topNode.rnode;
 //Push that right child
 nodeStack.push(topNodeRight);
 //Check if the push values is equal to the required key
 //If it is the require element break
 if(topNodeRight.value == key )
 {
 break;
 }
 //To terminate the loop if no element is found....
 //it checks if the popped element is getting added again
 if( lastPoppedNode == topNodeRight)
 {
 present = false;
 break;
 }
 }
 }
 //Printing based on the boolean variable.
 if(present)
 {
 for(Node tempNode : nodeStack)
 {
 System.out.println(tempNode.value);
 }
 }
 else
 {
 System.out.println("Element is not present in the tree");
 }
}

• Simon Forsberg: "This code is working for all the elements except root." - Is it intended to work for root? If it is intended to work, then it is probably not a correct implementation.
• mc20: It is not intended to work for root

Answer 1

Step 1: use an IDE to reformat this nicely

Step 2: remove pointless comments

For example:

// if left of top is not null, push to stack.
// Check if the push values is equla to the required key
// If it is the require element break
if (topNodeLeft != null) {
 nodeStack.push(topNodeLeft);
 if (topNodeLeft.value == key)
 break;
}

The comment explained in English exactly what the code does. This is pointless. On closer look, pretty much all the comments in this code are pointless.

Step 3: rename variables to more readable names

For example:

• lnode -> left
• rnode -> right

Step 4: let your IDE guide you

Pay attention to the warnings and try to fix them. For example IntelliJ tells this:

• The variable temp is never used: delete it
• The Node topNode = rootNode; initialization is pointless, skip the initialization

Step 5: remove unnecessary elements

Look at every variable with suspicion. What's the purpose of topLeftNode? After the renaming above, we have this line:

 topNodeLeft = topNode.left;

Which doesn't make a whole lot of sense. Can't we use just topNode.left ? Yes we can.

Why is topNode declared outside of the while loop when it is only used inside the loop, and assigned on the first line of the loop? It's better to declare it inside:

 while (true) {
 Node topNode = nodeStack.peek();

Step 6: look for bugs in simple (degenerate) cases

The method crashes with EmptyStackException if the tree has only one node.

Same thing if the tree has only two nodes with the child in left position.

While fixing these bugs, you might find more opportunities to improve. Give it a try.

With the above suggestions, the code becomes this:

public void findPathFromRoot(Node rootNode, int key) {
 Stack<Node> nodeStack = new Stack<>();
 nodeStack.push(rootNode);
 boolean present = true;
 Node topNodeRight;
 while (true) {
 Node topNode = nodeStack.peek();
 topNodeRight = topNode.right;
 if (topNode.left != null) {
 nodeStack.push(topNode.left);
 if (topNode.left.value == key) {
 break;
 }
 } else if (topNodeRight != null) {
 nodeStack.push(topNodeRight);
 if (topNodeRight.value == key) {
 break;
 }
 } else {
 Node lastPoppedNode;
 do {
 lastPoppedNode = nodeStack.pop();
 topNode = nodeStack.peek();
 } while (topNode.right == null);
 topNodeRight = topNode.right;
 nodeStack.push(topNodeRight);
 if (topNodeRight.value == key) {
 break;
 }
 if (lastPoppedNode == topNodeRight) {
 present = false;
 break;
 }
 }
 }
 if (present) {
 for (Node tempNode : nodeStack) {
 System.out.println(tempNode.value);
 }
 } else {
 System.out.println("Element is not present in the tree");
 }
}

Step 7: Stop and think

Stop and Think

What algorithm are you actually trying to implement here? The top answer on the question you linked suggests using pre-order traversal. That's a good suggestion that will work, though it won't be the fastest for all possible trees. I suggest to implement that algorithm first.