CODEWITHSUNDEEP
javatree
user2998228
user2998228

Reputation: 241

Find path to node in Tree?

I have a tree class that looks like:

Class Tree {
   Node root;
   Node curNode;
   public List<String> find(String value) {
      if (curNode == null) curNode = root;
        for (Node child : curNode.children) {
            if (found == false) {
                if (child.data.equals(value)) {
                    // if it finds it return the path to this node.
                }
                curNode = child;
                findDFS(value);
            }
        }
   }


class Node {
   List<Node> children;
   String data;
}

Where the tree root contains pointers to children nodes which point to other children etc etc. What I'm having problems with is once it finds the node, I need to return the the path to that node.

Upvotes: 5

Views: 12902

Answers (4)

vedavyasa k
vedavyasa k

Reputation: 1661

private static boolean treePathFinderRecurr(Node root, List<Character> path,Character target){
    
    if(root == null) {
        return false;
    }
    
    if(root.data == target || (treePathFinderRecurr(root.left,path,target) || treePathFinderRecurr(root.right,path,target))) {
        path.add(root.data);
        return true;
    }
    
    return false;
    
}

Upvotes: 0

Neha
Neha

Reputation: 41

The following code traces the path, adding nodes to the list and removing them if they are not in the path 

boolean getPath(Node root,String targetValue,List<Integer> path)
{
    // base case root is null so path not available
    if(root==null)
        return false;
    //add the data to the path
    path.add(root.getData());
    //if the root has data return true,path already saved
    if(root.getData().equals(targetValue))
        return true;
    //find the value in all the children
    for(Node child: children){
         if(getPath(child,targetValue,path))
          return true;
    }
    //if this node does not exist in path remove it
    path.remove(path.size()-1);
    return false;
}

Upvotes: 0

Easton L.
Easton L.

Reputation: 3034

passing a list tracking the path, once find the node, exit the recursion and fill the path one by one.

    Boolean Search(Node node, String value, List<Node> track)
    {
        if (node == null) return false;

        if (node.data.equals(value))
        {
            track.add(node);
            return true;
        }

        for(Node child : node.children)
        {
            if (Search(child, value, track)
            {
                track.add(0, node);
                return true;
            }
        }

        return false;
    }

Upvotes: 14

Ari
Ari

Reputation: 2004

If the nodes only point to their children, you'll need to keep track of each path on the way down. As mentioned in comment, you can do this with your own stack or with recursion. For example, you could always return find() call on the children of each node.

If the nodes point both ways, you can easily re-trace the path up once you find the correct node.

Upvotes: 0

Related Questions