Search the given key from both of the binary search trees. The key can be searched by selecting in each step the correct minimized tree where the search proceeds.

Click the triangles to expand the correct subtrees during the search.

Search(Node root, Key k)
1 if (root == null) //failed search
2   return null;
3 if (k == root.key) //succesfull search
4   return root;
5 if (k < root.key) //k in left branch
6   return Search(root.left, k);
7 else //k > root.key, i.e. k in right branch
8   return Search(root.right, k);