leetCodeTree.java

// 700. Search in a Binary Search Tree
// link: https://leetcode.com/problems/search-in-a-binary-search-tree/
// Solution: recursive
// Time O(n), Space O(n)
public TreeNode searchBST(TreeNode root, int val) {
    if (root == null) { return null; }
    if (root.val == val) { return root; }

    TreeNode node = root.val < val 
                    ? searchBST(root.right, val)
                    : searchBST(root.left, val);

    return node;
}



// Solution 2: iterative
// Time O(n), Space O(n)
public TreeNode searchBST(TreeNode root, int val) {
    Stack<TreeNode> stack = new Stack<TreeNode>(); 
    stack.push(root);

    while (!stack.empty()) {
        TreeNode node = stack.pop();
        if (node == null) { continue; }
        if (node.val == val) { return node; }
        if (node.val < val) {
            stack.push(node.right);
        } else {
            stack.push(node.left);
        }
    }

    return null;
}