Path to Node in a Binary Tree

Question

I am trying to recursively display the path taken to a given node in a binary tree where the method will output the path needed in the following way: "left, right, left". Here is what I have so far:

public static void pathToNode(BTNode p, char target, String res){
    if(p.data == target){
        res = res + p.data;
        System.out.println(res);
        return;
    }else if(res != null){
        if(res.charAt(0) == 'S'){
        res = res + p.data;
        }
    }else{
        pathToNode(p.leftLink, target, res);
        pathToNode(p.leftLink, target, res);
    }

}

This code is intended to just print out the path like so: "ABCD". Having done this I intend on making the method print out either left of right based on the correct option for each node traversal. Any Ideas?

Answer 1

Your code is a little unclear to me. Is 'S' supposed to be the root payload? Also, you should really try to use more telling variable names.

public static String pathToNode(BTNode p, char target) {
    // termination rules
    if (p.data == target) {
       // success
       return p.data;       
    }
    // failure: p is not the target AND is a leaf.
    if (p.leftLink == null && p.rightLink == null) return null;

    // recursion: if p is in the subtree, this will find it.
    return (pathToNode(p.leftLink, target) == null) ? (p.data + pathToNode(p.rightLink), target) : (p.data + pathToNode(p.leftLink, target));

}

edit: This may, of course, return null after all, if the target is not in the tree. Also, I forgot to actually print the path. It's in there now.

Answer 2

You're printing the result when you find the target you're looking for in the first if clause. Alternatively, you should try both the left and the right branches of the tree, what you (almost, you're doing left twive) do in the last clause.

I'm not sure what the second clause is supposed to be doing, but removing it and adding p.data to res in the recursive call should make sure the 'current' step is saved in the res variable:

if (p.data == target) {
    res = res + p.data;
    System.out.println(res);
} else {
    pathToNode(p.leftLink, target, res + p.data);
    pathToNode(p.rightLink, target, res + p.data);
}

This way, you're using a traditional base case + recursive case common to recursive algorithms.

Answer 3

I think you are trying to find the path from the root. Also I am assuming the tree will have only one path to on target. I mean same element cant be in different places in the tree.

This code will work,

public static void pathToNode(BTNode p, char target, String res){
    if(p.data == target){
        res += p.data;
        System.out.println(res);
        return;
    }
    else{
        if(res==null){
           res="";
        }
        res += p.data;
        pathToNode(p.leftLink, target, res);
        pathToNode(p.rightLink, target, res);
    }
}

But this will be very inefficient and memory cost easy solution. Please read more about tree traversal to have a good solution.