2.1 Search in BST

Assumption: may or may not have a parent field

Input: TreeNode root, int target

Output: TreeNode node with target value

Solution 1: Iterative

1. Search stop condition: root == null && root.key == target

2. Return root;

class TreeNode {
  TreeNode left;
  TreeNode right;
  //TreeNode parent;
  int key;
  public TreeNode(int key) {
    this.key = key;
  }
}

public class Solution {
  public TreeNode search(TreeNode root, int target) {
    while (root != null && root.key != target) {
      if (root.key < target) {
        root = root.right;
      } else {
        root = root.left;
      }
    }
    return root;
  }
}

Solution 2: Recursive

1. Base case: root == null || root.key == target

2. Breakpoint: same as in iterative

public TreeNode search(TreeNode root, int target) {
  if (root == null || root.target) { return root; }
  if (root.key > target) { 
    return search(root.left, target); 
  } else { 
   return search(root.right, target); 
  }
}