How to search for a node in a tree and return it?

Question

I'm trying to search for a node in a binary tree and return in case it's there, otherwise, return null. By the way, the node class has a method name() that return a string with it's name...What I have so far is:

private Node search(String name, Node node){

     if(node != null){
         if(node.name().equals(name)){
            return node;
         }

      else{
         search(name, node.left);
         search(name, node.right);
      }
    }
    return null;
}

Is this correct??

Answer 1

Boolean FindInBinaryTreeWithRecursion(TreeNode root, int data)
{
    Boolean temp;
    // base case == emptytree
    if (root == null) return false;
    else {
        if (data == root.getData())  return true;
        else { // otherwise recur down tree
            temp = FindInBinaryTreeWithRecursion(root.getLeft(), data);
            if (temp != true) 
                return temp;
            else
                return (FindInBinaryTreeWithRecursion(root.getRight(), data));  
        }
    }
}

Answer 2

This might be better:

if(node != null){
    if(node.name().equals(name)){
        return node;
    }
    else {
        Node tmp = search(name, node.left);
        if (tmp != null) { // if we find it at left
            return tmp; // we return it
        }
        // else we return the result of the search in the right node
        return search(name, node.right);
    }
}
return null;

Answer 3

Since language doesn't matter much for this question, here's what it looks in C# with pre-order traversal:

public static Node FindNode(Node n, int nodeValue)
{
    if (n == null) return null;
    if (n.Value == nodeValue) return n;
    return FindNode(n.Left, nodeValue) ?? FindNode(n.Right, nodeValue);
}

Answer 4

You need to make sure your recursive calls to search return if the result isn't null.

Something like this should work...

private Node search(String name, Node node){
    if(node != null){
        if(node.name().equals(name)){
           return node;
        } else {
            Node foundNode = search(name, node.left);
            if(foundNode == null) {
                foundNode = search(name, node.right);
            }
            return foundNode;
         }
    } else {
        return null;
    }
}