Clash Royale CLAN TAG

Leaf to Root Path Java

I have been searching around but can't seem to understand how to return path from leaf to root.

For Example:

A
/
B C
/ /
D E F


So if I do A.find(E) it should return [A,C,E] and if I do B.find(D) it should return [B,D]

A.find(E)

[A,C,E]

B.find(D)

[B,D]

My attempt :

// Base Case - The root of this Tree is c. Route is just [child]
public List<Person> find(Person c) {
List<Person> path = new ArrayList<Person>();
Person p = c;
while(c != null) {
path.add(p);
}
return path;
}


I... can't seem to understand how to return path from leaf to root.

find()

Person

1 Answer
1

Here is a solution for your question: searching from any start node to the specified target node in the tree:

public class PathFind {
public static void main(String... args) {
Node dNode = new Node("D", null, null);
Node bNode = new Node("B", dNode, null);

Node eNode = new Node("E");
Node fNode = new Node("F");
Node cNode = new Node("C", eNode, fNode);

Node aNode = new Node("A", bNode, cNode);

System.out.println(aNode.find(null));
System.out.println(aNode.find(bNode));
System.out.println(aNode.find(cNode));
System.out.println(aNode.find(eNode));
System.out.println(bNode.find(dNode));

System.out.println(bNode.find(eNode));
System.out.println(cNode.find(dNode));
}


static class Node {
Node left, right;
String val;

public Node(String theVal, Node theLeft, Node theRight) {
this.val = theVal;
this.left = theLeft;
this.right = theRight;
}

public Node(String theVal) {
this(theVal, null, null);
}

@Override
public String toString() {
return val;
}

public List<Node> find(Node theNode) {
List<Node> path = new ArrayList<>();
if (find(this, theNode, path)) return path;
else return null;
}



//

/**
*
* @param startNode start from the startNode to search;
* @param theNode the node to search;
* @param path using a list to record the path along the way;
* @return to indicate whether there is a path or not;
*/
private boolean find(Node startNode, Node theNode, List<Node> path) {
path.add(startNode);
if (startNode == theNode) return true;
if (startNode == null) return false;
if (find(startNode.left, theNode, path)) return true;
else path.remove(path.size() - 1); // remove the last for the right search;
if (find(startNode.right, theNode, path)) return true;
else path.remove(path.size() - 1);
return false;
}
}

}


There are three cases covered to ensure it will meet the requirement:

null

path

null

The output for the demo provided above:

[A, B, D, null]
[A, B]
[A, C]
[A, C, E]
[B, D]
null
null


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.