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

    def isValidBST(self, root: TreeNode) -> bool:
        return self.helper(root, -sys.maxsize + 1, sys.maxsize)

    def helper(self, curt, minv, maxv) :
        if not curt:
            return True
        if curt.val <= minv or curt.val >= maxv:
            return False
        return self.helper(curt.left, minv, curt.val) and self.helper(curt.right, curt.val, maxv)

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

    def closestValue(self, root: TreeNode, target: float) -> int:
        self.res = root.val
        self.helper(root, target)
        return self.res
    
    def helper(self, curt, target) :
        if not curt:
            return
        if abs(curt.val - target) < abs(self.res - target):
            self.res = curt.val
        if target < curt.val:
            self.helper(curt.left, target)
        else:
            self.helper(curt.right, target)

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;
        }
    }