4
\$\begingroup\$

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

}
\$\endgroup\$
2
  • \$\begingroup\$ "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. \$\endgroup\$ Feb 25, 2015 at 21:04
  • \$\begingroup\$ It is not intended to work for root \$\endgroup\$
    – mc20
    Feb 25, 2015 at 21:14

1 Answer 1

3
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.