Given a binary search tree and a "target" value, search the tree to see if it contains the target. The basic pattern of
the lookup() code occurs in many recursive tree algorithms: deal with the base case where the tree is empty, deal
with the current node, and then use recursion to deal with the subtrees. If the tree is a binary search tree, there is
often some sort of less-than test on the node to decide if the recursion should go left or right.
Given a binary tree, return true if a node
with the target data is found in the tree. Recurs
down the tree, chooses the left or right
branch by comparing the target to each node.
static int lookup(struct node* node, int target) {
// 1. Base case == empty tree
// in that case, the target is not found so return false
if (node == NULL) {
else {
// 2. see if found here
if (target == node->data) return(true);
else {
// 3. otherwise recur down the correct subtree
if (target < node->data) return(lookup(node->left, target));
else return(lookup(node->right, target));