Clash Royale CLAN TAG

Path from given node to root in a binary tree

I've been trying to figure this problem out for a while now and I'm not really getting anywhere with it. Essentially, given some binary tree and a node on that tree, how would you find the path from that given node back to the root?

Does anyone have an idea on how I could implement this? Any input would be greatly appreciated, my sincere thanks from a novice coder.

1 Answer
1

In order to find the path from one node to another, you have to recursively traverse the tree from the origin node down to its children, their children, and so on until you get to the destination node. Once you get to the destination node, you need to backtrack the path of nodes that took you to that destination node back to the root. One way to do this is a modified version of pre-order traversal in which one first checks the root, then its left subtree, and then its right subtree.

public boolean getPath(root, value){
if(root == null){
return false;
}
if(root.value === value){
System.out.println(root.value);
return true;
}
int onPath = getPath(root.left, value);
if(onPath){
System.out.println(root.value);
return true;
}
onPath = getPath(root.right,value);
if(onPath){
System.out.println(root.value);
return true;
}
return false; //a path was never found
}


In the method above, we compare the value of root with the destination value. If they are not equal we check the left subtree. If the destination is not in the left subtree we then check the right subtree. If the destination still is not found, false is returned so that when going back up the recursion call stack, we can let the node's parent know that there is no path to the destination from that node. If however, the destination is found, then we return true so that when going back up the recursion call stack we can tell the node's parent and its parent and so on that a path has been found.

root

value

false

true

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.