Understanding recursive search

Searching for a value in a binary search tree can be implemented by piggybacking on any of the binary tree traversal algorithms (which would visit every node, giving O(N) time where N is the number of nodes). However, if we observe the special property of a binary search tree (given below), we can quickly develop an exponentially faster algorithm (O(h) time, where h is the tree's height, so O(logN) for a balanced tree).

• All nodes in a node's left subtree are less in value than the node's value.
• All nodes in a node's right subtree are greater in value than the node's value.

Algorithm