6

I am trying to trace the path of a node in a binary tree (not a binary search tree). Given a node, I am trying to print the values of the path from the root.

alt text

I have written the following program.

package dsa.tree;

import java.util.Stack;

public class TracePath {
    private Node n1;

    public static void main(String args[]){
        TracePath nodeFinder = new TracePath();
        nodeFinder.find();
    }

    public void find(){
        Tree t = getSampleTree();
        tracePath(t,n1);
    }

    private Tree getSampleTree() {
        Tree bsTree = new BinarySearchTree();
        int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
        for(int i=0;i<randomData.length;i++){
            bsTree.add(randomData[i]);
        }
        n1 = bsTree.search(76);
        return bsTree;
    }

    public void tracePath(Tree t, Node node){
        trace(t,node);
    }

    Stack<Node> mainStack = new Stack<Node>();

    public void trace(Tree t, Node node){
        trace(t.getRoot(),node);
    }

    private void trace(Node parent, Node node){
        mainStack.push(parent);
        if(node.data == parent.data){
            for(Node iNode:mainStack){
                System.out.println(iNode.data);
            }
            return;
        }
        if(parent.left != null){
            trace(parent.left, node);
        }
        if(parent.right!=null){
            trace(parent.right, node);
        }
        mainStack.pop();
    }
}

I am getting the output properly. But its kind of messy. If you see the method trace(Node, Node), I am printing the values which I should not do. I want the trace method to properly complete. At least, I should kill the recursive structure at the stage i encounter the if condition.

Please advise.

5 Answers 5

6

Okay, you need to kill the recursion once you find your node. Simple enough. Change your trace method to return a boolean telling us if the node was found. That way, we go right back up the tree immediately after finding the node.

private boolean trace(Node parent, Node node){
    mainStack.push(parent);
    if(node.data == parent.data){
        for(Node iNode:mainStack){
            System.out.println(iNode.data);
        }
        return true;
    }
    if(parent.left != null){
        if (trace(parent.left, node)) return true;
    }
    if(parent.right!=null){
        if (trace(parent.right, node)) return true;
    }
    mainStack.pop();
    return false;
}
4
  • Excellent!!! Thank you very much.. Now I've experienced how to terminate/come out of recursive method.. Thanks again!
    – bragboy
    Feb 11, 2010 at 19:52
  • Now that you gave a "solution" instead of a homework hint, I will edit my answer to show what I meant.
    – rsp
    Feb 11, 2010 at 21:39
  • Solution posted at : technicalypto.com/2010/02/trace-path-of-binary-tree.html Thanks.
    – bragboy
    Feb 12, 2010 at 21:05
  • You could also simplify your nested if statements, for instance: if (parent.left != null) { return trace(parent.left, node); } May 10, 2016 at 17:48
3

I assume this is homework, so I will give some pointers instead of some code.

  • your trace method does a recursive descent, therefore the stack is not needed - you can build the path structure while returning from a found node
  • if your method uses a boolean or List return value , you can print the path while returning, or build up a list with the Nodes to print after the search method returns

Edit: If the path node to root is wanted, a simple boolean return suffices:

private boolean trace(Node parent, Node node) {
    boolean found = (node.data == parent.data)

    if (!found && parent.left != null) {
        found = trace(parent.left, node);
    }
    if (!found && parent.right != null){
        found = trace(parent.right, node);
    }

    if (found) {
        System.out.println(parent.data);
    }

    return found;
}

If you need the path from root to node, you can pass a List to receive the nodes in order:

private boolean trace(Node parent, Node node, List path) {
    boolean found = (node.data == parent.data)

    if (!found && parent.left != null) {
        found = trace(parent.left, node);
    }
    if (!found && parent.right != null){
        found = trace(parent.right, node);
    }

    if (found) {
        path.add(0, parent);
    }

    return found;
}

alternatively you can build the path on your way back and return as a list.

private List trace(Node parent, Node node) {
    List path = null;

    if (null != node) {
        if (node.data == parent.data) {

            path = new ArrayList();
        } else {
            path = trace(parent.left, node);

            if (null == path) {
                path = trace(parent.right, node);
            }
        }
        if (null != path) {
            path.add(0, parent);
        }
    }
    return path;
}
3
  • Thanks for hints.. My doubt is how to terminate this program?
    – bragboy
    Feb 11, 2010 at 19:40
  • You're wrong, he needs the stack. If he gets rid of it and just prints then, it'll print the leaf, then the leaf's parent, then it's parent, back up to the root. He needs the reverse of that printed, so the Stack is necessary to store the path.
    – Schmelter
    Feb 11, 2010 at 19:41
  • @Schmelter, I gave 2 possible return values, a boolean when node to root is wanted or a list that is built when the node is found otherwise. A stack that receives all nodes the algorithm visits is not needed.
    – rsp
    Feb 11, 2010 at 21:37
1

Something like this ?

public Stack<Node> findPath(Node src, Node dest, Stack<Node> alreadyCollected) {
    if (src == dest) 
        return alreadyCollected;
    if (src.left == null && src.right == null)
        return null;
    if (src.left != null) {
        Stack<Node> toTheLeft = new Stack<Node>(alreadyCollected);
        toTheLeft.push(src.left);
        Stack<Node> result = findPath(src.left, dest, toTheLeft);
        if (result != null)
            return result;
    }
    List<Node> toTheRight = new Stack<Node>(alreadyCollected);
    return findPath(src.right, dest, toTheRight);
}
1
  • Thanks for your response. i feel you are creating too many new Stack() inside a recursive loop. Looks costly to me.
    – bragboy
    Feb 11, 2010 at 20:02
1

Here is a recursive function without any use of stack. A recursion is equivalent to stack techincally and you must not need stack when doing recusrion.

PS: I am writing a pseudo code. Rewrite it yourself to get it compiled :)

bool trace(Node curr, Node n, Path path){
    if(curr == null)
        return;
    if(n == curr){
        path.insertAtEnd(curr);
        return true;
    }

    if(trace(curr.left, n, path)){
        path.insertAtEnd(curr);
        return true;
    }
    if(trace(curr.right, n, path)){
        path.insertAtEnd(curr);
        return true;
    }
    return false
}
4
  • Variable path is just an array and no where it is being used as a stack (LIFO). Feb 11, 2010 at 20:39
  • Your code work smoothly!!!! Thank you very much Niraj.. Yes, stack does an extra pop operation which is not needed when this can be done this way.
    – bragboy
    Feb 11, 2010 at 21:21
  • Just FYI, the converted code looks like private boolean trace(Node curr, Node n, List<Node> path){ if(curr == null) return false; if(n == curr){ path.add(curr); return true; } if(trace(curr.left, n, path)){ path.add(curr); return true; } if(trace(curr.right, n, path)){ path.add(curr); return true; } return false; }
    – bragboy
    Feb 11, 2010 at 21:21
  • One thing you may have noted: You can compare references instead of data. A BST can contain same data many times and then comparing data will result into a bug. Feb 11, 2010 at 21:34
0

Return a boolean from trace and decide whether or not to continue searching based on the value being returned from the recursive call.

Your Answer

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

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