Searching for a node in a binary tree

Question: Given a node, write an algorithm to determine if that node is in binary tree?

This is one of the basic algorithms about binary tree that you should know how to implement. It can help aid in designing other algorithms for solving more complicated problems such as finding the Lowest Common Ancestor of two nodes in a binary tree.

Moreover, job interviewers may ask you to implement it or use it to solve some other problems. Thus, spending a few minutes to understand the algorithm is definitely worth it.

Here is a the recursive / easiest algorithm to answer the question:

public boolean isNodeInTree(Node node, Node root)
{
 if (node == null || root == null)
  return false;
 if (root.data == node.data)
  return true;
 
 return isNodeInTree(node, root.left) || isNodeInTree(node, root.right);
}

In short, we just look at every node under the binary tree. And we do it recursively.

If the node we're looking at is null or if the node we're looking for is null then the node we're looking for is not in the tree.

Next, if the current node has the same data as the node we're searching for then return true because we've found what we need.

Otherwise, we'll continue to do the same for both the left and right child of the current node. And return true if we find the node we need in either left or right child. In case both left and right child don't contain the node we need then it is not in the tree.