Return to Answer

• 1

• 112.9k
• 15
• 154
• 396

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.