Binary Search Tree

Validate BST

• Time: O(N)
• Space: O(1)

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

private boolean isValidBST(TreeNode root, int min, int max) {
    if (root == null) {
        return true;
    }
    if (root.val < min && root.val > max) {
        return false;
    }
    return isValidBST(root.left, min, root.val) 
        && isValidBST(root.right, root.val, max);
}

Find the kth smallest element in BST

• Time: O(h)
• Space: O(1)

class KthSmallestElementinaBST {
    int count = 0;
    int ret = 0;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return ret;
    }

    public void inorder(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        inorder(root.left, k);
        count++;
        if (count == k) {
            ret = root.val;
            return;
        }
        inorder(root.right, k);
    }
}

Implement an iterator over a binary search tree (BST). Average O(1) time and uses O(h) memory

• Time: O(1)
• Space: O(h)

class BSTIterator {
    Stack<TreeNode> stack;
    TreeNode current;

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

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

    /** @return the next smallest number */
    public int next() {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        TreeNode node = current;
        current = current.right;
        return node.val;
    }
}