How to search for a node in a binary 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??

Have you tried running it to see if the results are correct? Why do you think it might *not* be correct? — FrustratedWithFormsDesigner, May 09 '11 at 14:44
Have you tried it? Making a test case is one of the most important parts of coding. — josh.trow, May 09 '11 at 14:44

Tom Jefferys · Accepted Answer · 2015-05-26T07:12:34.323

32

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;
    }
}

edited May 26 '15 at 07:12

answered May 09 '11 at 14:47

Tom Jefferys

13,090
2
35
36

You forgot a semicolon after return foundNode; – Jason Chen May 24 '15 at 05:11
Fantastic, this works like a charm, but I found this thread because I was having issues with my own recursive method...the note about ensuring you return null if the result isn't null saved my day – ViaTech Apr 10 '18 at 17:14
Nice! It's a bit of a mind bender but it works a treat! – AFM-Horizon Feb 19 '20 at 12:31

Puneet · Answer 2 · 2015-08-12T11:08:01.657

public Node findNode(Node root, Node nodeToFind) {
    Node foundNode = null;
    Node traversingNode = root;

    if (traversingNode.data == nodeToFind.data) {
        foundNode = traversingNode;
        return foundNode;
    }

    if (nodeToFind.data < traversingNode.data
            && null != traversingNode.leftChild) {
        findNode(traversingNode.leftChild, nodeToFind);
    } else if (nodeToFind.data > traversingNode.data
            && null != traversingNode.rightChild) {
        findNode(traversingNode, nodeToFind);
    }

    return foundNode;

}

score 1 · Answer 3 · answered Jun 22 '16 at 13:57

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);
}

score 0 · Answer 4 · edited Oct 03 '14 at 07:37

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));  
        }
    }
}

score 0 · Answer 5 · answered Jun 25 '15 at 21:33

public static TreeNode findNodeInTree(TreeNode root, TreeNode nodeToFind) {
  if (root == null) {
    return null;
  }

  if (root.data == nodeToFind.data) {
    return root;
  }

  TreeNode found = null;
  if (root.left != null) {
    found = findNodeInTree(root.left, nodeToFind);
    if (found != null) {
      return found;
    }
  }

  if (root.right != null) {
    found = findNodeInTree(root.right, nodeToFind);
    if (found != null) {
      return found;
    }
  }
  return null;
}

score 0 · Answer 6 · answered Jan 05 '16 at 13:57

Actually, try to avoid recursivity. In case you have big tree structure you will get stack overflow error. Instead of this you can use a list:

private Node search(String name, Node node){
    List<Node> l = new ArrayList<Node>();
    l.add(node);
    While(!l.isEmpty()){
        if (l.get(0).name().equals(name))   
            return l.get(0);
        else {
            l.add(l.get(0).left);
            l.add(l.get(0).right);
            l.remove(0);
        }           
    }   
    return null;
}

score 0 · Answer 7 · answered May 02 '18 at 15:19

public static boolean findElement(Node root, int value) {
    if (root != null) {
        if (root.data == value) {
            return true;
        } else {
            return findElement(root.left, value) || findElement(root.right, value);
        }
    }
    return false;
}

score 0 · Answer 8 · answered Jul 27 '19 at 19:53

0

    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null || root.val==val) return root;
        TreeNode found = (val < root.val) ? searchBST(root.left,val) : searchBST(root.right,val);
        return found;
    }

View Code on GitHub

answered Jul 27 '19 at 19:53

RCT

1,044
1
5
12

You should add some explanation to your answer. – m02ph3u5 Jul 27 '19 at 20:24

bfontaine · Answer 9 · 2011-05-09T14:51:48.257

0

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;

edited May 09 '11 at 14:51

answered May 09 '11 at 14:45

bfontaine

18,169
13
73
107

return null; at the end might give compile warning (depending on configuration) because it is unreachable code. – amit May 09 '11 at 15:05
you are right, missed the big if statement at the top. my mistake. – amit May 09 '11 at 16:29

score 0 · Answer 10 · answered May 09 '11 at 14:46

0

you should return something if it is found in node.left or node.right so the else block should be something like that:

 else{
     Node temp = search(name, node.left);
     if (temp != null) return temp;
     temp = search(name, node.right);
     if (temp != null) return temp;
  }

answered May 09 '11 at 14:46

amit

175,853
27
231
333

A `return null` statement is needed at the end of `else` body o handle the case if key is not found. – haccks May 07 '15 at 07:55

score 0 · Answer 11 · answered May 09 '11 at 14:47

0

you don't do anything with the result of the recursive calls

Node res = search(name, node.left);
if(res!=null)return res;
res = search(name, node.right);
if(res!=null)return res;

answered May 09 '11 at 14:47

ratchet freak

47,288
5
68
106

score 0 · Answer 12 · answered Mar 04 '20 at 02:36

private TreeNode findX(TreeNode root, int x) {
    if(root == null) return null;
    if(root.val == x) return root;

    TreeNode left = findX(root.left,x);
    TreeNode right = findX(root.right,x);

    if(left == null) return right;
    return left;

}

score 0 · Answer 13 · answered Jul 18 '20 at 12:33

0

Node* search(Node* root,int key){
   
   // If key is found or is NULL     
   if (root == NULL || root->key == key) 
      return root;

   if (root->key < key) 
      return search(root->right, key); 
   
   return search(root->left, key);
}

answered Jul 18 '20 at 12:33

Dhruv Patel

1
1

score 0 · Answer 14 · answered Apr 08 '22 at 13:50

For C++ guys:

//search in a binary tree | O(n)
TreeNode* searchBST(TreeNode* root, int val) {
    if(!root) return root;
    if(root->val == val) return root;

    TreeNode* temp = searchBST(root->left, val);
    if(!temp){
        temp = searchBST(root->right, val);
    }
    return temp;
}

//search in a BST | O(logn)
TreeNode* searchBST(TreeNode* root, int val) {
    if(!root) return root;
    if(root->val == val) return root;
    if(val < root->val) return searchBST(root->left, val);
    return searchBST(root->right, val);
}

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

14 Answers14

Linked