BST or Inorder

701. Insert into a Binary Search Tree

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

98. Validate Binary Search Tree

Java

public boolean isValidBST(TreeNode root) {
    return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean helper(TreeNode curt, long min, long max) {
    if (curt == null) return true;
    if (curt.val <= min || curt.val >= max) return false;
    return helper(curt.left, min, curt.val) 
        && helper(curt.right, curt.val, max);
}

Python

450. Delete Node in a BST

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key == root.val) {
        if (root.left == null && root.right == null) {
            return null;
        } else if (root.right == null) {
            return root.left;
        } else {
            TreeNode swap = findSwap(root.right);
            root.val = swap.val;
            root.right = deleteNode(root.right, swap.val);
        }
    } else if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

private TreeNode findSwap(TreeNode curt) {
    while (curt.left != null) {
        curt = curt.left;
    }
    return curt;
}

235. Lowest Common Ancestor of a Binary Search Tree

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } 
    return root;
}

865. Smallest Subtree with all the Deepest Nodes

An upgrade version of 235. Need to output LCA as well as count depth.

public TreeNode subtreeWithAllDeepest(TreeNode root) {
    return helper(root).node;
}

private Result helper(TreeNode root) {
    if (root == null) {
        return new Result(0, null);
    }
    Result L = helper(root.left);
    Result R = helper(root.right);
    if (L.depth > R.depth) {
        return new Result(L.depth + 1, L.node);
    } else if (L.depth < R.depth) {
        return new Result(R.depth + 1, R.node);
    }
    return new Result(L.depth + 1, root);
}

class Result {
    int depth;
    TreeNode node;
    public Result(int depth, TreeNode node) {
        this.depth = depth;
        this.node = node;
    }
}

538. Convert BST to Greater Tree

Reverse in-order traversal, add the increment to the node and update the increment.

int val = 0;
public TreeNode convertBST(TreeNode root) {
    helper(root);
    return root;
}

private void helper(TreeNode curt) {
    if (curt == null) return;
    helper(curt.right);
    curt.val += val;
    val = curt.val;
    helper(curt.left);
}

270. Closest Binary Search Tree Value

Java

public int closestValue(TreeNode root, double target) {
    return helper(root, root.val, target);
}

private int helper(TreeNode root, int min, double target) {
    if (root == null) return min;
    
    if (Math.abs(root.val - target) < Math.abs(min - target)) {
        min = root.val;
    }
    if (root.val > target) {
        min = helper(root.left, min, target);
    } else {
        min = helper(root.right, min, target);
    }
    return min;
}

Python

272. Closest Binary Search Tree Value II

Inorder traversal the tree and maintain a list. Treat the list as a deque or linkedlist. Add nodes to the back, pop first if the first nodes is farther than curt val. Therefore all nodes in the list are the closest to target when the list size is larger than k. When the first node is closer target than current node. It means all results are found, return.

This is similar as sliding window on an array and maintain the closest values.

public List<Integer> closestKValues(TreeNode root, double target, int k) {
    LinkedList<Integer> list = new LinkedList<>();
    helper(root, target, k, list);
    return list;
}

private void helper(TreeNode root, double target, int k, LinkedList<Integer> list) {
    if (root == null) return;
    helper(root.left, target, k, list);
    if (list.size() >= k) {
        if (!list.isEmpty() && Math.abs(list.peekFirst() - target) > Math.abs(root.val - target)) {
            list.pollFirst();
        } else {
            return;
        }
    }
    list.add(root.val);
    helper(root.right, target, k, list);
}

938. Range Sum of BST

3 scenarios:

• L R < root.val

• root.val < L R

• L < root.val < R

sum = 0;
def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
    self.helper(root, L, R)
    return self.sum
    
def helper(self, root, L, R):
    if not root:
        return
    if root.val < L and root.val < R:
        self.helper(root.right, L, R)
    elif root.val > L and root.val > R:
        self.helper(root.left, L, R)
    else:
        self.sum += root.val
        self.helper(root.left, L, R)
        self.helper(root.right, L, R)

173. Binary Search Tree Iterator

Solution1. Inorder traversal and store all results in a list

Solution2: Iteration Inorder traversal by using Stack

    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushAll(root);
    }

    private void pushAll(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /** @return the next smallest number */
    public int next() {
        if (!hasNext()) return -1;
        TreeNode curt = stack.pop();
        pushAll(curt.right);
        return curt.val;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

Solution3: Morris traversal:

TreeNode curt;
public BSTIterator(TreeNode root) {
    this.curt = root;
}

/** @return the next smallest number */
public int next() {
    Integer res = null;
    while (curt != null) {
        if (curt.left == null) {
            res = curt.val;
            curt = curt.right;
            break;
        } else {
            TreeNode pre = curt.left;
            while (pre.right != null && pre.right != curt) {
                pre = pre.right;
            }
            if (pre.right == null) {
                pre.right = curt;
                curt = curt.left;
            } else {
                pre.right = null;
                res = curt.val;
                curt = curt.right;
                break;
            }
        }
    }
    return res;
}

/** @return whether we have a next smallest number */
public boolean hasNext() {
    return curt != null;
}

285. Inorder Successor in BST

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode succ = null;
    Stack<TreeNode> stack = new Stack<>();
    addLeft(root, stack);
    while (!stack.isEmpty()) {
        TreeNode pop = stack.pop();
        addLeft(pop.right, stack);
        if (pop == p && !stack.isEmpty()) {
            succ = stack.peek();   
            break;
        }
    }
    return succ;
}

private void addLeft(TreeNode curt, Stack<TreeNode> stack) {
    while (curt != null) {
        stack.add(curt);
        curt = curt.left;
    }
}

99. Recover Binary Search Tree

Inorder traverse this tree, use pre to record the previous node, at each node check if pre != null && A == null && pre.val >= curt.val. If so, set the A to pre, which means A is a candidate. if pre != null && A != null && pre.val >= curt.val then B is another candidate. For example,

A B

1 2 4 3 5

Then swap the value of A and B.

TreeNode A;
TreeNode B;
TreeNode pre;
public void recoverTree(TreeNode root) {
    helper(root);
    int temp = A.val;
    A.val = B.val;
    B.val = temp;
}

private void helper(TreeNode curt) {
    if (curt == null) return;
    helper(curt.left);
    if (pre != null && A == null && pre.val >= curt.val) {
        A = pre;     
    }
    if (pre != null && A != null && pre.val >= curt.val) {
        B = curt;
    }
    pre = curt;
    helper(curt.right);
}

1214. Two Sum BSTs

Two Sum approach: O(n^2)

public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
    if (root1 == null || root2 == null) return false;
    if (root1.val + root2.val == target) return true;
    else if (root1.val + root2.val > target) {
        return twoSumBSTs(root1.left, root2, target)
             || twoSumBSTs(root1, root2.left, target);
    } else {
        return twoSumBSTs(root1.right, root2, target)
             || twoSumBSTs(root1, root2.right, target);
    }
}

Set approach: T: O(n) S: O(n)

public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
    Set<Integer> set = new HashSet<>();
    traverse(root1, set);
    return traverse2(root2, set, target);
}

private void traverse(TreeNode root, Set<Integer> set) {
    if (root == null) return;
    set.add(root.val);
    traverse(root.left, set);
    traverse(root.right, set);
}

private boolean traverse2(TreeNode root, Set<Integer> set, int target) {
    if (root == null) return false;
    if (set.contains(target - root.val)) return true;
    return traverse2(root.left, set, target) || traverse2(root.right, set, target);
}

333. Largest BST Subtree

int max = 1;
public int largestBSTSubtree(TreeNode root) {
    if (root == null) {
        return 0;
    }
    helper(root);
    return max;
}

private Result helper(TreeNode root) {
    if (root == null) {
        return new Result(true, 0);
    }
    Result L = helper(root.left);
    Result R = helper(root.right);
    Result res = new Result(false, 0);
    int Lbound = L.max == null ? Integer.MIN_VALUE : L.max;
    int Rbound = R.min == null ? Integer.MAX_VALUE : R.min;
    if (L.isBST && R.isBST && root.val > Lbound && root.val < Rbound) {
        res.size = L.size + R.size + 1;
        res.min = L.min == null ? root.val : L.min;
        res.max = R.max == null ? root.val : R.max;
        res.isBST = true;
        max = Math.max(max, res.size);
        return res;
    } 
    return res;
}

class Result {
    Integer min, max;
    boolean isBST;
    int size;
    Result(boolean isBST, int size) {
        this.isBST = isBST;
        this.size = size;
    }
}