Tree Construction and Serialization

Construct Binary Tree from Pre-order and In-order Traversal (LeetCode 105)

Concept: The first element in a pre-order sequence is the root. Locate this root in the in-order sequence to partition the tree into left and right subtrees.

Map<Integer, Integer> inorderMap;

TreeNode buildTree(int[] preorder, int[] inorder) {
    inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

private TreeNode build(int[] pre, int pl, int pr, int il, int ir) {
    if (pl > pr) return null;
    
    int rootVal = pre[pl];
    int rootIdx = inorderMap.get(rootVal);
    int leftSize = rootIdx - il;
    
    TreeNode root = new TreeNode(rootVal);
    // Left subtree: [pl+1, pl+leftSize] in pre and [il, rootIdx-1] in in
    root.left  = build(pre, pl + 1, pl + leftSize, il, rootIdx - 1);
    // Right subtree: [pl+leftSize+1, pr] in pre and [rootIdx+1, ir] in in
    root.right = build(pre, pl + leftSize + 1, pr, rootIdx + 1, ir);
    
    return root;
}

Construct Binary Tree from Post-order and In-order Traversal (LeetCode 106)

Concept: The last element in the post-order sequence is the root.

private TreeNode build(int[] post, int pl, int pr, int il, int ir) {
    if (pl > pr) return null;
    
    int rootVal = post[pr]; // Last in post-order is root
    int rootIdx = inorderMap.get(rootVal);
    int leftSize = rootIdx - il;
    
    TreeNode root = new TreeNode(rootVal);
    root.left  = build(post, pl, pl + leftSize - 1, il, rootIdx - 1);
    root.right = build(post, pl + leftSize, pr - 1, rootIdx + 1, ir);
    
    return root;
}

Serialization and Deserialization (LeetCode 297)

Approach: Pre-order DFS

// Serialization
String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serializeDFS(root, sb);
    return sb.toString();
}

private void serializeDFS(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("null,");
        return;
    }
    sb.append(node.val).append(',');
    serializeDFS(node.left, sb);
    serializeDFS(node.right, sb);
}

// Deserialization
private int currentIdx = 0;

TreeNode deserialize(String data) {
    String[] nodes = data.split(",");
    return deserializeRebuild(nodes);
}

private TreeNode deserializeRebuild(String[] nodes) {
    if (currentIdx >= nodes.length || "null".equals(nodes[currentIdx])) {
        currentIdx++;
        return null;
    }
    
    TreeNode node = new TreeNode(Integer.parseInt(nodes[currentIdx++]));
    node.left = deserializeRebuild(nodes);
    node.right = deserializeRebuild(nodes);
    return node;
}

Reconstruct BST from Pre-order (LeetCode 1008)

Since it is a BST, we don't need the in-order sequence explicitly (it's essentially the sorted pre-order).

TreeNode bstFromPreorder(int[] preorder) {
    return buildBST(preorder, 0, preorder.length - 1);
}

private TreeNode buildBST(int[] pre, int left, int right) {
    if (left > right) return null;
    
    TreeNode root = new TreeNode(pre[left]);
    
    // Find the split point: first element greater than root belongs to the right subtree
    int i = left + 1;
    while (i <= right && pre[i] < pre[left]) {
        i++;
    }
    
    root.left = buildBST(pre, left + 1, i - 1);
    root.right = buildBST(pre, i, right);
    return root;
}

Lowest Common Ancestor (LCA, LeetCode 236)

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    // LCA found: p and q are split across current root
    if (left != null && right != null) return root;
    // Otherwise return whichever found signal exists
    return left != null ? left : right;
}

LCA of a Binary Search Tree (LeetCode 235)

Exploit BST property for O(h) iterative search:

TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        } else {
            // p and q split, or one is the root of the other
            return root;
        }
    }
    return null;
}