How to find a specific node in a non binary Tree?

Question

I have a tree that contains multiple nodes. Each node has a parent node (or null in the case of the root), a name (name), and a HashTable (children) that maps the name of the child node to the child node object.

Given the string name of the node, I want to create a method that iterates through the tree to find the specific node and return it. If the node doesn't exist then return null.

I thought a recursive method would be best. So far I have this:

public Node findNode(Node n, String s) {
   if (n.name == s) {
       return n;
   } else {
       for (Node child: n.children.values()) {
            findNode(child, s);
       }
     }
}

I'm not sure exactly where to put the null statement.

Nick Garvey · Accepted Answer · 2015-10-30 05:47:08Z

14

If a child has it, then return it. If not, then return null.

public Node findNode(Node n, String s) {
    if (n.name == s) {
        return n;
    } else {
        for (Node child: n.children.values()) {
            Node result = findNode(child, s);
            if (result != null) {
                return result;
            }
        }
    }
    return null;
}

answered Oct 30, 2015 at 5:47

Nick Garvey

3,0001 gold badge27 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

TheGabiRod Over a year ago

A great answer, I would like to note that the " if (result != null){... " inside the for is important to avoid returning null values instead of the not null searched. thanks!

Mihkel Selgal · Accepted Answer · 2020-12-01 13:03:57Z

1

Here is Java 11+ version using Optional to search for the node.

public Optional<Node> search (Node node, String needle) {
    if (node.getValue().equals(needle)) {
        return Optional.of(node);
    } else {
        for (var child : node.getChildren()) {
            var result = search(child, needle);
            if (result.isPresent()) {
                return result;
            }
        }
    }

    return Optional.empty();
}

answered Dec 1, 2020 at 13:03

Mihkel Selgal

5086 silver badges13 bronze badges

Collectives™ on Stack Overflow

How to find a specific node in a non binary Tree?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related