Trees

A tree is a hierarchical data structure with nodes connected by edges. Binary Tree: each node has at most 2 children. BST (Binary Search Tree): left < root < right, enabling O(log n) search. Key traversals: Inorder (left-root-right, sorted for BST), Preorder (root-left-right), Postorder (left-right-root), Level order (BFS). Balanced BSTs (AVL, Red-Black) guarantee O(log n) operations.

Key Concepts

Deep Dive: Tree Traversals

// Inorder: Left → Root → Right (sorted order for BST)
public void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    process(root.val);
    inorder(root.right);
}

// Preorder: Root → Left → Right (copy a tree)
public void preorder(TreeNode root) {
    if (root == null) return;
    process(root.val);
    preorder(root.left);
    preorder(root.right);
}

// Postorder: Left → Right → Root (delete a tree)
public void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    process(root.val);
}

Iterative inorder using stack:

public List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) { stack.push(curr); curr = curr.left; }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

Deep Dive: Common Tree Problems

Max depth:

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Check if balanced:

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}
private int height(TreeNode root) {
    if (root == null) return 0;
    int left = height(root.left), right = height(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left, right);
}

Lowest Common Ancestor (BST):

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

Validate BST:

public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}

Common Interview Questions

• Maximum depth of a binary tree
• Validate BST
• Symmetric tree
• Level order traversal
• Lowest common ancestor
• Serialize and deserialize a binary tree
• Invert a binary tree
• Diameter of a binary tree
• Path sum
• Construct tree from traversals