In-Order Traversal

Recursive

List<Integer> inorder(TreeNode node) {
    List<Integer> out = new ArrayList<>();
    walk(node, out);
    return out;
}

void walk(TreeNode cur, List<Integer> acc) {
    if (cur == null) return;
    walk(cur.left, acc);
    acc.add(cur.val);
    walk(cur.right, acc);
}

Iterative (Single Stack)

List<Integer> inorder(TreeNode root) {
    List<Integer> res = 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();
        res.add(curr.val);
        curr = curr.right;
    }
    return res;
}

Unified Iterative Template (Pre/In/Post)

enum Color { WHITE, GRAY }

List<Integer> inorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<Pair<Color, TreeNode>> st = new ArrayDeque<>();
    if (root != null) st.push(new Pair<>(Color.WHITE, root));
    while (!st.isEmpty()) {
        Pair<Color, TreeNode> p = st.pop();
        TreeNode node = p.second;
        if (node == null) continue;
        if (p.first == Color.GRAY) {
            res.add(node.val);
        } else {
            st.push(new Pair<>(Color.WHITE, node.right));
            st.push(new Pair<>(Color.GRAY,   node));
            st.push(new Pair<>(Color.WHITE, node.left));
        }
    }
    return res;
}

Maximum Depth

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

Invert (Mirror) Binary Tree

TreeNode mirror(TreeNode root) {
    if (root == null) return null;
    TreeNode left  = mirror(root.left);
    TreeNode right = mirror(root.right);
    root.left  = right;
    root.right = left;
    return root;
}

Symmetric Tree

Recursive

boolean isSymmetric(TreeNode root) {
    return root == null || check(root.left, root.right);
}

boolean check(TreeNode l, TreeNode r) {
    if (l == null || r == null) return l == r;
    return l.val == r.val && check(l.left, r.right) && check(l.right, r.left);
}

Iteratiev (Queue)

boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root.left);
    q.offer(root.right);
    while (!q.isEmpty()) {
        TreeNode a = q.poll();
        TreeNode b = q.poll();
        if (a == null && b == null) continue;
        if (a == null || b == null || a.val != b.val) return false;
        q.offer(a.left);  q.offer(b.right);
        q.offer(a.right); q.offer(b.left);
    }
    return true;
}

Daimeter of Binary Tree

class Diameter {
    int best = 0;
    int dfs(TreeNode node) {
        if (node == null) return 0;
        int l = dfs(node.left);
        int r = dfs(node.right);
        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    }
    int diameter(TreeNode root) {
        dfs(root);
        return best;
    }
}

Level-Order Traversal (BFS)

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode cur = q.poll();
            level.add(cur.val);
            if (cur.left  != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        res.add(level);
    }
    return res;
}

Sorted Array to Balanced BST

TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

TreeNode build(int[] nums, int l, int r) {
    if (l > r) return null;
    int m = l + (r - l) / 2;
    TreeNode root = new TreeNode(nums[m]);
    root.left  = build(nums, l, m - 1);
    root.right = build(nums, m + 1, r);
    return root;
}

Validate BST

boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

boolean validate(TreeNode node, Integer lo, Integer hi) {
    if (node == null) return true;
    if ((lo != null && node.val <= lo) || (hi != null && node.val >= hi))
        return false;
    return validate(node.left, lo, node.val) && validate(node.right, node.val, hi);
}

K-th Smallest in BST

int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> st = new ArrayDeque<>();
    TreeNode curr = root;
    while (true) {
        while (curr != null) {
            st.push(curr);
            curr = curr.left;
        }
        curr = st.pop();
        if (--k == 0) return curr.val;
        curr = curr.right;
    }
}

Right Side View

List<Integer> rightSideView(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    dfs(root, 0, out);
    return out;
}

void dfs(TreeNode node, int depth, List<Integer> acc) {
    if (node == null) return;
    if (depth == acc.size()) acc.add(node.val);
    dfs(node.right, depth + 1, acc);
    dfs(node.left,  depth + 1, acc);
}

Flatten Binary Tree to Linked List

void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.left);
    flatten(root.right);
    TreeNode rightSubtree = root.right;
    root.right = root.left;
    root.left = null;
    TreeNode tail = root;
    while (tail.right != null) tail = tail.right;
    tail.right = rightSubtree;
}

Construct Tree from Preorder & Inorder

TreeNode buildTree(int[] pre, int[] in) {
    Map<Integer, Integer> idx = new HashMap<>();
    for (int i = 0; i < in.length; i++) idx.put(in[i], i);
    return build(pre, 0, pre.length - 1, in, 0, in.length - 1, idx);
}

TreeNode build(int[] pre, int pl, int pr, int[] in, int il, int ir, Map<Integer,Integer> idx) {
    if (pl > pr) return null;
    int rootVal = pre[pl];
    int rootPos = idx.get(rootVal);
    int leftSize = rootPos - il;
    TreeNode root = new TreeNode(rootVal);
    root.left  = build(pre, pl + 1, pl + leftSize, in, il, rootPos - 1, idx);
    root.right = build(pre, pl + leftSize + 1, pr, in, rootPos + 1, ir, idx);
    return root;
}

Path Sum III (Any Path)

Brute Force

int pathSum(TreeNode root, long target) {
    if (root == null) return 0;
    return fromRoot(root, target) + pathSum(root.left, target) + pathSum(root.right, target);
}

int fromRoot(TreeNode node, long rem) {
    if (node == null) return 0;
    int cnt = (node.val == rem) ? 1 : 0;
    rem -= node.val;
    return cnt + fromRoot(node.left, rem) + fromRoot(node.right, rem);
}

Prefix Sum + HashMap + Backtracking

int pathSum(TreeNode root, long target) {
    Map<Long, Integer> pre = new HashMap<>();
    pre.put(0L, 1);
    return dfs(root, target, 0L, pre);
}

int dfs(TreeNode node, long target, long curr, Map<Long,Integer> pre) {
    if (node == null) return 0;
    curr += node.val;
    int res = pre.getOrDefault(curr - target, 0);
    pre.merge(curr, 1, Integer::sum);
    res += dfs(node.left, target, curr, pre);
    res += dfs(node.right, target, curr, pre);
    pre.merge(curr, -1, Integer::sum);
    return res;
}

Lowest Common Ancestor (General Tree)

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left  = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    if (left == null) return right;
    if (right == null) return left;
    return root;
}

Maximum Path Sum (Any Path)

class MaxPath {
    int best = Integer.MIN_VALUE;
    int dfs(TreeNode node) {
        if (node == null) return 0;
        int l = Math.max(0, dfs(node.left));
        int r = Math.max(0, dfs(node.right));
        best = Math.max(best, node.val + l + r);
        return node.val + Math.max(l, r);
    }
    int maxPathSum(TreeNode root) {
        dfs(root);
        return best;
    }
}