Binary Tree

# python
# LC 298 - Binary Tree Longest Consecutive Sequence
# STYLE A: LOOK-BACK — recurse first, compare against the parent I was handed
# time = O(n), space = O(h)
class Solution(object):
    def longestConsecutive(self, root):
        if not root:
            return 0
        self.max_len = 0
        self.dfs(root, None, 0)      # seed: no parent -> streak resets to 1
        return self.max_len

    def dfs(self, node, parent, curr_len):
        if not node:                 # <-- null handled HERE (base case)
            return
        # I decide MY OWN state from my parent's
        if parent and node.val == parent.val + 1:
            curr_len += 1
        else:
            curr_len = 1             # streak broke -> restart AT me
        self.max_len = max(self.max_len, curr_len)

        # ALWAYS recurse both sides - a broken streak can restart anywhere below
        self.dfs(node.left, node, curr_len)
        self.dfs(node.right, node, curr_len)

# python
# LC 298 - Binary Tree Longest Consecutive Sequence
# STYLE B: LOOK-FORWARD — I compute each CHILD's state before calling it
# time = O(n), space = O(h)
class Solution(object):
    def longestConsecutive(self, root):
        if not root:
            return 0
        self.max_len = 0
        self.dfs(root, 1)            # seed: root is a streak of length 1
        return self.max_len

    def dfs(self, node, curr_len):
        self.max_len = max(self.max_len, curr_len)
        # I decide MY CHILDREN's state, and guard the null BEFORE recursing
        if node.left:                # <-- null handled HERE (call-site guard)
            self.dfs(node.left, curr_len + 1 if node.left.val == node.val + 1 else 1)
        if node.right:
            self.dfs(node.right, curr_len + 1 if node.right.val == node.val + 1 else 1)

# python
# LC 298 - the `parent_val` sentinel variant of Style A
# IDEA: seed with (root.val - 1) so the root automatically satisfies "val == parent_val + 1" -> length 1
dfs(root, root.val - 1, 0)     # no `if parent` branch needed inside dfs

Can I answer for this node using ONLY what I learned on the way down?
├── YES -> Top-Down. Pick Style A or B freely (they are interchangeable).
│         Root-to-leaf sums, depth, path constraints, "ancestor so far".
└── NO, I need a fact about my SUBTREE (its height / best path / sum)
          -> Bottom-Up (Style C). A and B CANNOT express this.
             Depth, diameter, max path sum, balance, subtree aggregates.

# python
# LC 298 - Style C (bottom-up): return "longest run STARTING at me, going down"
# IDEA: post-order; the global captures the best, the return value feeds my parent
# time = O(n), space = O(h)
def helper(node):
    if not node:
        return 0
    l, r = helper(node.left), helper(node.right)     # children FIRST
    cur = 1
    if node.left and node.left.val == node.val + 1:
        cur = max(cur, l + 1)
    if node.right and node.right.val == node.val + 1:
        cur = max(cur, r + 1)
    self.max_len = max(self.max_len, cur)            # global != return value
    return cur

# python
# IDEA: carry the current streak down; a break restarts it at 1 and keeps exploring
# time = O(n), space = O(h)
# LC 298 - Binary Tree Longest Consecutive Sequence
def longestConsecutive(root):
    best = 0

    def dfs(node, parent, curr_len):
        nonlocal best
        if node is None:
            return
        if parent and node.val == parent.val + 1:
            curr_len += 1
        # ✅ correct - streak breaks: restart at 1, but keep exploring
        else:
            curr_len = 1
            # 🚫 wrong here: `return` - a longer streak may start deeper in this subtree

        best = max(best, curr_len)
        # recurse on BOTH children whether the streak continued or reset
        dfs(node.left, node, curr_len)
        dfs(node.right, node, curr_len)

    dfs(root, None, 0)
    return best

    1
     \
      2        longest = 4  (1 -> 2 -> 3 -> 4)
     /
    3
     \
      4

# python
# LC 102 - Binary Tree Level Order Traversal (the DFS version)
# IDEA: carry depth as an argument; the first visit to a depth opens its list
# time = O(n), space = O(h)
def nodes_by_depth(root):
    levels = []

    def dfs(node, depth):
        if node is None:
            return
        if depth == len(levels):          # first node seen at this depth
            levels.append([])
        levels[depth].append(node.val)
        dfs(node.left, depth + 1)         # the child's depth is decided HERE, by the parent
        dfs(node.right, depth + 1)

    dfs(root, 0)
    return levels


# python
# Depth of one target node (edges from the root), -1 if it is not in the tree
# IDEA: pre-order DFS carrying depth; the -1 sentinel means "not below me"
# time = O(n), space = O(h)
def depth_of(root, target):
    def dfs(node, depth):
        if node is None:
            return -1
        if node is target:
            return depth
        left = dfs(node.left, depth + 1)
        if left != -1:                    # found on the left: stop, skip the right
            return left
        return dfs(node.right, depth + 1)

    return dfs(root, 0)

        10
       /  \
     15    20
    / \    /
   30 40  50

# `n is an "index"` in array

Index:   1   2   3   4   5   6
Value: [10, 15, 20, 30, 40, 50]

# python
# LC 94 - Binary Tree Inorder Traversal
# IDEA: recurse left, record the node, recurse right; move the append to get pre- or post-order
# time = O(n), space = O(h)   h = height of the tree (recursion stack)
def inorderTraversal(root):
    result = []

    def dfs(node):
        if not node:
            return
        # result.append(node.val)   <- here: PRE-order  (root, left, right)
        dfs(node.left)
        result.append(node.val)     # here: IN-order   (left, root, right)
        dfs(node.right)
        # result.append(node.val)   <- here: POST-order (left, right, root)

    dfs(root)
    return result

// java
// LC 94 - Binary Tree Inorder Traversal
// IDEA: recurse left, record the node, recurse right; move the add() for pre- or post-order
// time = O(n), space = O(h)
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    dfs(root, result);
    return result;
}

private void dfs(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    dfs(node.left, result);
    result.add(node.val);           // in-order position
    dfs(node.right, result);
}

# python
# LC 102 - Binary Tree Level Order Traversal
# IDEA: snapshot the queue length = the size of the current level, drain exactly that many
# time = O(n), space = O(w)   w = maximum width of a level
from collections import deque

def levelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)          # every node now in the queue is on this level
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result


# LC 94 - Binary Tree Inorder Traversal (iterative)
# IDEA: push the whole left spine, pop = visit, then move to the right child
# time = O(n), space = O(h)
def inorder_iterative(root):
    result = []
    stack = []
    current = root
    while current or stack:
        while current:                   # go as far left as possible
            stack.append(current)
            current = current.left
        current = stack.pop()            # leftmost unvisited node
        result.append(current.val)
        current = current.right          # its right subtree comes next
    return result

// java
// LC 102 - Binary Tree Level Order Traversal
// IDEA: snapshot the queue size = the current level, drain exactly that many
// time = O(n), space = O(w)
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();     // read ONCE, before the loop adds children
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        result.add(level);
    }
    return result;
}

# python
# LC 105 - Construct Binary Tree from Preorder and Inorder Traversal
# IDEA: next preorder value is the root; its inorder index splits [lo, hi] into left / right
# time = O(n), space = O(n)   the index map, plus O(h) recursion
def buildTree(preorder, inorder):
    index_of = {}
    for i, val in enumerate(inorder):
        index_of[val] = i                 # O(1) lookup instead of inorder.index()
    pre_index = 0                         # next root to take from preorder

    def build(lo, hi):                    # build the subtree whose values are inorder[lo..hi]
        nonlocal pre_index
        if lo > hi:
            return None
        root_val = preorder[pre_index]
        pre_index += 1
        root = TreeNode(root_val)
        mid = index_of[root_val]
        root.left = build(lo, mid - 1)    # left FIRST: preorder lists the left subtree next
        root.right = build(mid + 1, hi)
        return root

    return build(0, len(inorder) - 1)

// java
// LC 105 - Construct Binary Tree from Preorder and Inorder Traversal
// IDEA: next preorder value is the root; its inorder index splits the range
// time = O(n), space = O(n)
private Map<Integer, Integer> indexOf = new HashMap<>();
private int preIndex = 0;

public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
        indexOf.put(inorder[i], i);
    }
    preIndex = 0;
    return build(preorder, 0, inorder.length - 1);
}

private TreeNode build(int[] preorder, int lo, int hi) {
    if (lo > hi) {
        return null;
    }
    int rootVal = preorder[preIndex];
    preIndex++;
    TreeNode root = new TreeNode(rootVal);
    int mid = indexOf.get(rootVal);
    root.left = build(preorder, lo, mid - 1);    // left before right
    root.right = build(preorder, mid + 1, hi);
    return root;
}

preorder = [3,9,20,15,7]   inorder = [9,3,15,20,7]
build(0,4)  root 3  mid 1  -> left = build(0,0), right = build(2,4)
build(0,0)  root 9  mid 0  -> both children build(lo > hi) = None
build(2,4)  root 20 mid 3  -> left = build(2,2) root 15, right = build(4,4) root 7
result      [3,9,20,null,null,15,7]

# python
# LC 543 - Diameter of Binary Tree
# IDEA: return my height (in nodes) to my parent; record the path that bends at me
# time = O(n), space = O(h)
def diameterOfBinaryTree(root):
    best = 0                               # longest path seen so far, in edges

    def height(node):
        nonlocal best
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)     # the path that bends at node
        return 1 + max(left, right)        # only ONE arm continues upward

    height(root)
    return best

// java
// LC 543 - Diameter of Binary Tree
// IDEA: return the height, record left + right in a field
// time = O(n), space = O(h)
private int best = 0;

public int diameterOfBinaryTree(TreeNode root) {
    best = 0;
    height(root);
    return best;
}

private int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = height(node.left);
    int right = height(node.right);
    best = Math.max(best, left + right);
    return 1 + Math.max(left, right);
}

# python
# LC 222 - Count Complete Tree Nodes
# IDEA: compare the left spines of the two subtrees; the perfect half is counted by 2^h,
#       recurse only into the other half
# time = O(log^2 n), space = O(log n)
def countNodes(root):
    if not root:
        return 0

    def left_depth(node):                  # nodes on the leftmost path
        depth = 0
        while node:
            depth += 1
            node = node.left
        return depth

    left_h = left_depth(root.left)
    right_h = left_depth(root.right)
    if left_h == right_h:
        # left subtree is perfect: 2^left_h - 1 nodes, plus the root = 2^left_h
        return (1 << left_h) + countNodes(root.right)
    # right subtree is perfect, one level shorter: 2^right_h - 1 nodes, plus the root
    return (1 << right_h) + countNodes(root.left)

// java
// LC 222 - Count Complete Tree Nodes
// IDEA: equal left spines -> left half perfect, else right half perfect; recurse into the other
// time = O(log^2 n), space = O(log n)
public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftH = leftDepth(root.left);
    int rightH = leftDepth(root.right);
    if (leftH == rightH) {
        return (1 << leftH) + countNodes(root.right);
    }
    return (1 << rightH) + countNodes(root.left);
}

private int leftDepth(TreeNode node) {
    int depth = 0;
    while (node != null) {
        depth++;
        node = node.left;
    }
    return depth;
}

# python
# LC 222 - Count Complete Tree Nodes (same-node spines)
# IDEA: leftmost depth == rightmost depth -> perfect subtree -> 2^h - 1; else 1 + both children
# time = O(log^2 n), space = O(log n)   one child is always perfect and returns at once
def countNodes(root):
    if not root:
        return 0
    left_h, node = 0, root
    while node:                            # leftmost spine
        left_h += 1
        node = node.left
    right_h, node = 0, root
    while node:                            # rightmost spine
        right_h += 1
        node = node.right
    if left_h == right_h:
        return (1 << left_h) - 1
    return 1 + countNodes(root.left) + countNodes(root.right)

# python
# LC 117 - Populating Next Right Pointers in Each Node II
# IDEA: walk level k through its own `next` chain; build level k+1's chain with dummy + tail
# time = O(n), space = O(1)   output pointers not counted
def connect(root):
    cur = root                       # head of the level being walked
    while cur:
        dummy = Node(0)              # dummy.next will be the head of the NEXT level
        tail = dummy
        while cur:                   # walk the current level through `next`
            if cur.left:
                tail.next = cur.left
                tail = tail.next
            if cur.right:
                tail.next = cur.right
                tail = tail.next
            cur = cur.next
        cur = dummy.next             # drop down one level
    return root

// java
// LC 117 - Populating Next Right Pointers in Each Node II
// IDEA: traverse level k via its own `next` chain; build level k+1's chain with dummy + tail
// time = O(n), space = O(1)
public Node connect(Node root) {
    Node cur = root;
    while (cur != null) {
        Node dummy = new Node(0);
        Node tail = dummy;
        while (cur != null) {
            if (cur.left != null) {
                tail.next = cur.left;
                tail = tail.next;
            }
            if (cur.right != null) {
                tail.next = cur.right;
                tail = tail.next;
            }
            cur = cur.next;
        }
        cur = dummy.next;
    }
    return root;
}

# python
# LC 337 - House Robber III
# IDEA: post-order DP returning (take, skip) per subtree
# time = O(n), space = O(h)
def rob(root):
    def helper(node):
        if not node:
            return (0, 0)                     # (take, skip)
        left = helper(node.left)
        right = helper(node.right)
        take = node.val + left[1] + right[1]  # robbing me forces both children to be skipped
        skip = max(left) + max(right)         # skipping me leaves each child free
        return (take, skip)

    return max(helper(root))

// java
// LC 337 - House Robber III
// IDEA: post-order DP; each call returns {take, skip}
// time = O(n), space = O(h)
public int rob(TreeNode root) {
    int[] res = robHelper(root);
    return Math.max(res[0], res[1]);
}

private int[] robHelper(TreeNode node) {
    if (node == null) {
        return new int[]{0, 0};
    }
    int[] l = robHelper(node.left);
    int[] r = robHelper(node.right);
    int take = node.val + l[1] + r[1];
    int skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
    return new int[]{take, skip};
}

LC 337 example 1: [3,2,3,null,3,null,1]
leaf 3 -> (3, 0)     leaf 1 -> (1, 0)
node 2 (right child 3) -> take = 2 + 0 + 0 = 2,  skip = 0 + max(3,0) = 3   -> (2, 3)
node 3 (right child 1) -> take = 3 + 0 + 0 = 3,  skip = 0 + max(1,0) = 1   -> (3, 1)
root 3 -> take = 3 + 3 + 1 = 7,  skip = max(2,3) + max(3,1) = 6            -> answer 7

# python
# LC 652 - Find Duplicate Subtrees
# IDEA: canonical subtree id string + Counter; two subtrees are equal iff their ids are equal
# time = O(n^2) worst case (string building), space = O(n^2)
from collections import Counter

def findDuplicateSubtrees(root):
    count = Counter()
    result = []

    def subtree_id(node):
        if not node:
            return "#"                     # null marker keeps ids unambiguous
        key = "%s,%s,%s" % (node.val, subtree_id(node.left), subtree_id(node.right))
        count[key] += 1
        if count[key] == 2:                # report each duplicate exactly once
            result.append(node)
        return key

    subtree_id(root)
    return result

// java
// LC 652 - Find Duplicate Subtrees
// IDEA: serialize every subtree into a canonical id string, count ids in a map.
//       Use a null marker ("#") - without it "1,2" is ambiguous.
// time = O(n^2) worst case (string building), space = O(n^2)
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    Map<String, Integer> cnt = new HashMap<>();
    List<TreeNode> res = new ArrayList<>();
    subtreeId(root, cnt, res);
    return res;
}

private String subtreeId(TreeNode node, Map<String, Integer> cnt, List<TreeNode> res) {
    if (node == null) {
        return "#";
    }
    String key = node.val + ","
            + subtreeId(node.left, cnt, res) + ","
            + subtreeId(node.right, cnt, res);
    int c = cnt.merge(key, 1, Integer::sum);
    if (c == 2) {   // == 2 (not >= 2) so each duplicate is reported once
        res.add(node);
    }
    return key;
}

// java
// LC 549 - Binary Tree Longest Consecutive Sequence II
// IDEA: post-order DP. Each call returns {inc, dec} = longest ascending / descending
//       consecutive run STARTING at this node and going straight down.
//       The bent (child -> node -> child) path is scored into a global, not returned.
/**
 * time = O(N), space = O(H)   // H = tree height (recursion stack)
 */
private int res = 0;

public int longestConsecutive(TreeNode root) {
    helper(root);
    return res;
}

// returns int[]{ inc, dec }
private int[] helper(TreeNode node) {
    if (node == null) {
        return new int[]{0, 0};
    }
    int[] l = helper(node.left);
    int[] r = helper(node.right);

    int inc = 1, dec = 1;   // the node alone is already a run of length 1
    /** null-check the child BEFORE reading child.val */
    if (node.left != null) {
        if (node.left.val == node.val + 1) {
            inc = Math.max(inc, l[0] + 1);
        } else if (node.left.val == node.val - 1) {
            dec = Math.max(dec, l[1] + 1);
        }
    }
    if (node.right != null) {
        if (node.right.val == node.val + 1) {
            inc = Math.max(inc, r[0] + 1);
        } else if (node.right.val == node.val - 1) {
            dec = Math.max(dec, r[1] + 1);
        }
    }

    // the path is allowed to BEND here: descending arm + this node + ascending arm
    res = Math.max(res, inc + dec - 1);

    // only the STRAIGHT runs are usable by the parent
    return new int[]{inc, dec};
}

# python
# LC 549 - Binary Tree Longest Consecutive Sequence II
# IDEA: post-order DP returning (inc, dec) per subtree; bent path scored into a global
class Solution:
    def longestConsecutive(self, root):
        # time = O(N), space = O(H)
        self.res = 0

        def helper(node):
            if not node:
                return (0, 0)                   # (inc, dec)

            l_inc, l_dec = helper(node.left)
            r_inc, r_dec = helper(node.right)

            inc = dec = 1                       # the node alone is a run of length 1
            if node.left:
                if node.left.val == node.val + 1:
                    inc = max(inc, l_inc + 1)
                elif node.left.val == node.val - 1:
                    dec = max(dec, l_dec + 1)
            if node.right:
                if node.right.val == node.val + 1:
                    inc = max(inc, r_inc + 1)
                elif node.right.val == node.val - 1:
                    dec = max(dec, r_dec + 1)

            # bend at THIS node: descending arm + node + ascending arm
            self.res = max(self.res, inc + dec - 1)
            return (inc, dec)                   # straight runs only go up

        helper(root)
        return self.res

      2         helper(1) -> (inc=1, dec=1)      leaf
     / \        helper(3) -> (inc=1, dec=1)      leaf
    1   3       at node 2:  left.val 1 == 2 - 1  -> dec = l_dec + 1 = 2
                            right.val 3 == 2 + 1 -> inc = r_inc + 1 = 2
                answer here = inc + dec - 1 = 2 + 2 - 1 = 3     (1 -> 2 -> 3)
                returns (2, 2) upward — NOT 3, a bent path cannot be extended

# python
# LC 1110 - Delete Nodes And Return Forest
# IDEA: return None to detach a deleted node; pass `is_root` (my parent was deleted) down
# time = O(n), space = O(n)   the set of values to delete, plus O(h) recursion
def delNodes(root, to_delete):
    to_del = set(to_delete)
    forest = []

    def walk(node, is_root):
        if not node:
            return None
        deleted = node.val in to_del
        if is_root and not deleted:
            forest.append(node)                    # I survive and nobody points at me
        node.left = walk(node.left, deleted)       # my children are roots iff I am deleted
        node.right = walk(node.right, deleted)
        return None if deleted else node           # None detaches me from my parent

    walk(root, True)
    return forest

// java
// LC 1110 - Delete Nodes And Return Forest
// IDEA: DFS carrying `isRoot`; a deleted node returns null, which detaches it from its parent
// time = O(n), space = O(n)
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
    Set<Integer> toDel = new HashSet<>();
    for (int v : to_delete) {
        toDel.add(v);
    }
    List<TreeNode> forest = new ArrayList<>();
    walk(root, true, toDel, forest);
    return forest;
}

private TreeNode walk(TreeNode node, boolean isRoot, Set<Integer> toDel, List<TreeNode> forest) {
    if (node == null) {
        return null;
    }
    boolean deleted = toDel.contains(node.val);
    if (isRoot && !deleted) {
        forest.add(node);
    }
    node.left = walk(node.left, deleted, toDel, forest);
    node.right = walk(node.right, deleted, toDel, forest);
    return deleted ? null : node;
}

# python
# LC 1110 - Delete Nodes And Return Forest (BFS variant)
# IDEA: the parent decides: detach a deleted child; a deleted parent hands its survivors to the forest
# time = O(n), space = O(n)
from collections import deque

def delNodes(root, to_delete):
    to_del = set(to_delete)
    forest = [] if root.val in to_del else [root]
    queue = deque([root])
    while queue:
        node = queue.popleft()
        for side in ("left", "right"):
            child = getattr(node, side)
            if not child:
                continue
            queue.append(child)
            if child.val in to_del:
                setattr(node, side, None)          # detach the deleted child
            elif node.val in to_del:
                forest.append(child)               # survivor under a deleted parent
    return forest

# python
# LC 814 - Binary Tree Pruning
# IDEA: prune both children first, THEN test whether I became a zero-valued leaf
# time = O(n), space = O(h)
def pruneTree(root):
    if not root:
        return None
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)
    if root.val == 0 and not root.left and not root.right:
        return None
    return root

// java
// LC 814 - Binary Tree Pruning
// IDEA: prune children first, THEN test if I became a valueless leaf
// time = O(n), space = O(h)
public TreeNode pruneTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);
    if (root.val == 0 && root.left == null && root.right == null) {
        return null;
    }
    return root;
}

# python
# LC 662 - Maximum Width of Binary Tree
# IDEA: BFS with (node, heap_index); re-base each level to 0; width = last - first + 1
# time = O(n), space = O(w)   w = maximum width of a level
from collections import deque

def widthOfBinaryTree(root):
    if not root:
        return 0
    best = 0
    queue = deque([(root, 0)])
    while queue:
        level_size = len(queue)
        first = queue[0][1]                   # index of the leftmost node on this level
        last = 0
        for _ in range(level_size):
            node, index = queue.popleft()
            index -= first                    # re-base to 0 so indices stay small
            last = index
            if node.left:
                queue.append((node.left, 2 * index))
            if node.right:
                queue.append((node.right, 2 * index + 1))
        best = max(best, last + 1)
    return best

// java
// LC 662 - Maximum Width of Binary Tree
// IDEA: BFS carrying the heap-style index; re-base each level so the int never overflows
// time = O(n), space = O(w)
public int widthOfBinaryTree(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int best = 0;
    Deque<TreeNode> nodes = new ArrayDeque<>();
    Deque<Integer> idx = new ArrayDeque<>();
    nodes.offer(root);
    idx.offer(0);
    while (!nodes.isEmpty()) {
        int size = nodes.size();
        int first = idx.peek();
        int last = 0;
        for (int i = 0; i < size; i++) {
            TreeNode n = nodes.poll();
            int j = idx.poll() - first;       // re-based index
            last = j;
            if (n.left != null) {
                nodes.offer(n.left);
                idx.offer(2 * j);
            }
            if (n.right != null) {
                nodes.offer(n.right);
                idx.offer(2 * j + 1);
            }
        }
        best = Math.max(best, last + 1);
    }
    return best;
}

# python
# LC 662 - Maximum Width of Binary Tree (DFS variant)
# IDEA: pre-order, left first; the first index seen at each depth is that level's leftmost
# time = O(n), space = O(h)   plus one entry per level in first_index
def widthOfBinaryTree(root):
    first_index = {}                       # depth -> index of the leftmost node seen there
    best = 0

    def dfs(node, depth, index):
        nonlocal best
        if not node:
            return
        if depth not in first_index:       # pre-order, left first: the first visit is leftmost
            first_index[depth] = index
        best = max(best, index - first_index[depth] + 1)
        dfs(node.left, depth + 1, 2 * index)
        dfs(node.right, depth + 1, 2 * index + 1)

    dfs(root, 0, 0)
    return best

LC 662 example 1: [1,3,2,5,3,null,9]
level 0: (1,0)                     first 0  last 0   width 1
level 1: (3,0) (2,1)               first 0  last 1   width 2
level 2: (5,0) (3,1) (9,3)         first 0  last 3   width 4   <- the null at index 2 counts

# python
# LC 958 - Check Completeness of a Binary Tree
# IDEA: BFS that enqueues null children too; in a complete tree every real node comes first
# time = O(n), space = O(w)
from collections import deque

def isCompleteTree(root):
    queue = deque([root])
    seen_null = False
    while queue:
        node = queue.popleft()
        if not node:
            seen_null = True
        else:
            if seen_null:
                return False          # a real node after a hole -> not complete
            queue.append(node.left)   # push nulls on purpose
            queue.append(node.right)
    return True

// java
// LC 958 - Check Completeness of a Binary Tree
// IDEA: BFS enqueuing nulls too. In a complete tree all real nodes come first.
// time = O(n), space = O(w)
public boolean isCompleteTree(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();   // LinkedList, because ArrayDeque rejects null
    q.add(root);
    boolean seenNull = false;
    while (!q.isEmpty()) {
        TreeNode n = q.poll();
        if (n == null) {
            seenNull = true;
        } else {
            if (seenNull) {
                return false;
            }
            q.add(n.left);
            q.add(n.right);
        }
    }
    return true;
}

# python
# LC 100 - Same Tree
# IDEA: recurse on (p, q) pairs; both None = equal, one None = different, then compare values
# time = O(min(n, m)), space = O(min(h1, h2))   stops at the first difference
def isSameTree(p, q):
    if not p and not q:                    # both ran out together
        return True
    if not p or not q:                     # only one ran out: shapes differ
        return False
    if p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

// java
// LC 100 - Same Tree
// IDEA: recurse on (p, q) pairs; both null = equal, one null = different, then compare values
// time = O(min(n, m)), space = O(min(h1, h2))
public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }
    if (p.val != q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Problem Analysis Flowchart:

1. Does the problem require visiting nodes in specific order?
   ├── YES → Use Traversal Templates (1 or 2)
   │   ├── Need all nodes level by level? → Level Order (Template 2)
   │   ├── Need specific order (pre/in/post)? → Template 1
   │   └── Need iterative approach? → Template 2
   └── NO → Continue to 2

2. Does the problem involve building/modifying tree structure?
   ├── YES → Use Construction Template (3)
   │   ├── From traversal sequences? → Template 3
   │   ├── From array/string? → Template 3 variant
   │   └── Serialize/Deserialize? → Custom Template 3
   └── NO → Continue to 3

3. Does the problem involve paths from root to leaves?
   ├── YES → Use Path Template (4)
   │   ├── Need all paths? → Template 4 with result collection
   │   ├── Need path sum? → Template 4 with sum tracking
   │   └── Need max/min path? → Template 4 with optimization
   └── NO → Continue to 4

4. Does the problem ask for tree properties?
   ├── YES → Use Property Template (5)
   │   ├── Height/Depth? → Template 5 basic
   │   ├── Balance/Symmetry? → Template 5 with comparison
   │   └── Diameter/Width? → Template 5 with global max
   └── NO → Continue to 5

5. Does the problem involve finding ancestors or distances?
   ├── YES → Use LCA Template (6)
   │   ├── Common ancestor? → Template 6
   │   └── Distance between nodes? → Template 6 + path tracking
   └── NO → Continue to 6

6. Does the problem require O(log n) time or involve complete/balanced tree optimization?
   ├── YES → Use Binary Search on Trees Template (7)
   │   ├── Complete binary tree? → Template 7 with height optimization
   │   ├── BST with kth element? → Template 7 with inorder traversal
   │   └── Need log time complexity? → Template 7 with binary search
   └── NO → Use Template 1 (plain recursion) or reconsider problem type

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')
        
        def helper(node):
            if not node:
                return 0
            left = max(0, helper(node.left))
            right = max(0, helper(node.right))
            self.max_sum = max(self.max_sum, left + right + node.val)
            return max(left, right) + node.val
        
        helper(root)
        return self.max_sum

def rightSideView(root):
    if not root:
        return []
    result, queue = [], [root, None]
    
    while queue:
        node = queue.pop(0)
        if node:
            if queue[0] is None:  # Last node in level
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        elif queue:  # Level delimiter
            queue.append(None)
    
    return result

// Java TreeNode definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

// Use Queue interface with LinkedList
Queue<TreeNode> queue = new LinkedList<>();

// Stack for iterative traversal
Stack<TreeNode> stack = new Stack<>();

# TreeNode definition
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Use collections.deque for O(1) operations
from collections import deque
queue = deque([root])

# List as stack (append/pop)
stack = []