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

def dfs(node, parent, curr_len):
    if node is None:
        return
    if parent and node.val == parent.val + 1:
        curr_len += 1
    # ✅ correct - streak breaks, but keep exploring
    else:
        curr_len = 1
        dfs(node.left, node, curr_len)

    # 🚫 wrong - a longer streak may start deeper in this same subtree
    # else:
    #     return

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

        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]

def tree_problem(root):
    """
    Universal template for most binary tree problems
    Can be adapted for traversal, calculation, or modification
    """
    # Base case
    if not root:
        return None  # or 0, [], depending on problem
    
    # Pre-order processing (before recursion)
    # process_current_node()
    
    # Recursive calls
    left_result = tree_problem(root.left)
    right_result = tree_problem(root.right)
    
    # Post-order processing (after recursion)
    # combine_results()
    
    return result

# Preorder Traversal
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Inorder Traversal  
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Postorder Traversal
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Iterative Inorder with Stack
def inorder_iterative(root):
    result, stack = [], []
    current = root
    
    while current or stack:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left
        
        # Current must be None, so pop from stack
        current = stack.pop()
        result.append(current.val)
        
        # Visit right subtree
        current = current.right
    
    return result

# Level Order with Queue
def level_order(root):
    if not root:
        return []
    
    result = []
    queue = collections.deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

def build_tree_from_traversals(preorder, inorder):
    """
    Construct tree from preorder and inorder traversals
    Key insight: First element in preorder is always root
    """
    if not preorder or not inorder:
        return None
    
    # Root is first element in preorder
    root = TreeNode(preorder[0])
    
    # Find root position in inorder to split left/right
    root_idx = inorder.index(root.val)
    
    # Recursively build subtrees
    # Left subtree: elements before root in inorder
    root.left = build_tree_from_traversals(
        preorder[1:root_idx+1],  # Skip root, take left elements
        inorder[:root_idx]       # Everything before root
    )
    
    # Right subtree: elements after root in inorder
    root.right = build_tree_from_traversals(
        preorder[root_idx+1:],   # Everything after left subtree
        inorder[root_idx+1:]     # Everything after root
    )
    
    return root

def path_sum_template(root, target):
    """
    Template for path sum problems
    Can track paths, sums, or other properties
    """
    def dfs(node, current_sum, path):
        if not node:
            return
        
        # Update current state
        current_sum += node.val
        path.append(node.val)
        
        # Check if leaf node and condition met
        if not node.left and not node.right:
            if current_sum == target:
                result.append(path[:])  # Copy current path
        
        # Explore subtrees
        dfs(node.left, current_sum, path)
        dfs(node.right, current_sum, path)
        
        # Backtrack
        """
        NOTE !!! why do we need backtrack here ? (gemini)
        In simple terms, **backtracking** is the "undo" button for your recursion.


        ### 3. A Visual Example

        Imagine this tree:

        ```text
            1
           / \
           2   3

        ```text

        **Without `path.pop()`:**

        1. Go to `1`: `path = [1]`
        2. Go to `2`: `path = [1, 2]`
        3. Finish `2`, go back to `1`.
        4. Go to `3`: `path = [1, 2, 3]`  <-- **ERROR!** (2 shouldn't be here)

        **With `path.pop()`:**

        1. Go to `1`: `path = [1]`
        2. Go to `2`: `path = [1, 2]`
        3. Finish `2`, **`pop()`**: `path = [1]`
        4. Go to `3`: `path = [1, 3]` <-- **CORRECT!**
        """
        path.pop()
    
    result = []
    dfs(root, 0, [])
    return result

def tree_property_template(root):
    """
    Calculate tree properties (height, diameter, balance)
    """
    def helper(node):
        if not node:
            return 0  # or (0, True) for multiple values
        
        # Get info from subtrees
        left_info = helper(node.left)
        right_info = helper(node.right)
        
        # Calculate current node's property
        current_property = calculate(left_info, right_info)
        
        # Update global result if needed
        self.result = max(self.result, current_property)
        
        return current_property
    
    self.result = 0
    helper(root)
    return self.result

def find_lca(root, p, q):
    """
    Find lowest common ancestor of nodes p and q
    """
    if not root or root == p or root == q:
        return root

    left = find_lca(root.left, p, q)
    right = find_lca(root.right, p, q)

    # Both found in different subtrees -> current is LCA
    if left and right:
        return root

    # One or both found in same subtree
    return left if left else right

# python
# LC 1650 - Lowest Common Ancestor of a Binary Tree III
# IDEA: 2 pointers on the parent chain; on hitting null, restart at the OTHER node
#       -> each pointer walks len(path(p)) + len(path(q)) steps, so they meet at the LCA
# time = O(h), space = O(1)
class Solution(object):
    def lowestCommonAncestor(self, p, q):
        # edge
        if not p or not q:
            return None

        a, b = p, q
        while a != b:
            # NOTE !!! `if a else q`, NOT `a.parent or q` -- the None step itself
            #          must be consumed, or the two walks differ by one and never meet
            a = a.parent if a else q
            b = b.parent if b else p
        return a

def count_complete_tree_nodes(root):
    """
    Count nodes in complete binary tree in O(log²n) time
    Key: Use binary search on tree structure
    """
    if not root:
        return 0

    def get_height(node):
        """Get height by going left"""
        height = 0
        while node:
            height += 1
            node = node.left
        return height

    left_height = get_height(root.left)
    right_height = get_height(root.right)

    if left_height == right_height:
        # Left subtree is perfect binary tree
        # Nodes in left = 2^left_height - 1
        # Plus root = 2^left_height
        return (1 << left_height) + count_complete_tree_nodes(root.right)
    else:
        # Right subtree is perfect binary tree
        # Height = right_height, nodes = 2^right_height - 1
        # Plus root = 2^right_height
        return (1 << right_height) + count_complete_tree_nodes(root.left)

// 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
//       using a dummy node + tail pointer. No queue needed.
/**
 * time = O(N), space = O(1)   // output pointers not counted
 */
public Node connect(Node root) {
    Node cur = root;                 // head of the level being traversed
    while (cur != null) {
        Node dummy = new Node(0);    // sentinel: dummy.next = head of NEXT level
        Node tail = dummy;           // grows the next level's chain

        while (cur != null) {        // walk current level via `next`
            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;            // drop down one level
    }
    return root;
}

# python
# LC 117 - Populating Next Right Pointers in Each Node II
# IDEA: same as java - dummy head + tail builds the next level's `next` chain
class Solution:
    def connect(self, root):
        # time = O(N), space = O(1)
        cur = root
        while cur:
            dummy = Node(0)      # sentinel for the NEXT level
            tail = dummy
            while cur:           # walk 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     # move down
        return root

// java
// LC 337 - House Robber III
// IDEA: post-order DP. Each call returns {maxIfWeRobThisNode, maxIfWeSkipThisNode}.
//       Robbing a node forbids robbing its children -> must use children's "skip".
/**
 * time = O(N), space = O(H)   // H = tree height (recursion stack)
 */
public int rob(TreeNode root) {
    int[] res = robHelper(root);
    return Math.max(res[0], res[1]);
}

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

    // rob current -> children MUST be skipped
    int take = node.val + l[1] + r[1];
    // skip current -> children are free to do whatever is best
    int skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);

    return new int[]{take, skip};
}

# python
# LC 337 - House Robber III
# IDEA: post-order DP returning (take, skip) per subtree
class Solution:
    def rob(self, root):
        # time = O(N), space = O(H)
        def helper(node):
            if not node:
                return (0, 0)             # (take, skip)
            l = helper(node.left)
            r = helper(node.right)
            take = node.val + l[1] + r[1]  # children must be skipped
            skip = max(l) + max(r)         # children free to choose
            return (take, skip)

        return max(helper(root))

// java
// LC 652 - Find Duplicate Subtrees
// IDEA: serialize every subtree into a canonical id string, count ids in a map.
//       Two subtrees are identical iff their ids are equal.
//       NOTE: 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;
}

# python
# LC 652 - Find Duplicate Subtrees
# IDEA: canonical subtree id string + Counter
class Solution:
    def findDuplicateSubtrees(self, root):
        # time = O(N^2) worst case, space = O(N^2)
        cnt = collections.Counter()
        res = []

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

        sid(root)
        return res

// 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
    /** NOTE !!! 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

// java
// LC 1110 - Delete Nodes And Return Forest
// IDEA: DFS carrying `isRoot` (= my parent was deleted / I am the original root).
//       A surviving node that is a root gets collected. A deleted node returns null,
//       which detaches it from its parent, and marks its children as new roots.
/**
 * 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);

    // I survive AND nobody points at me -> I head a tree in the forest
    if (isRoot && !deleted) {
        forest.add(node);
    }

    // children are "roots" exactly when I am deleted
    node.left = walk(node.left, deleted, toDel, forest);
    node.right = walk(node.right, deleted, toDel, forest);

    return deleted ? null : node;   // returning null detaches me from my parent
}

# python
# LC 1110 - Delete Nodes And Return Forest
# IDEA: same - return None to detach, pass `is_root` down
class Solution:
    def delNodes(self, root, to_delete):
        # time = O(N), space = O(N)
        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)
            # my children become roots iff I am deleted
            node.left = walk(node.left, deleted)
            node.right = walk(node.right, deleted)
            return None if deleted else node

        walk(root, True)
        return forest

// 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);

    // only decidable after children are pruned
    if (root.val == 0 && root.left == null && root.right == null) {
        return null;
    }
    return root;
}

# python
# LC 814 - Binary Tree Pruning
class Solution:
    def pruneTree(self, root):
        # time = O(N), space = O(H)
        if not root:
            return None
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if root.val == 0 and not root.left and not root.right:
            return None
        return root

// java
// LC 662 - Maximum Width of Binary Tree
// IDEA: BFS carrying the heap-style index of each node. Width of a level is
//       (index of last node) - (index of first node) + 1, so null gaps count.
/**
 * time = O(N), space = O(W)   // W = max level width
 */
public int widthOfBinaryTree(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int res = 0;
    Queue<TreeNode> nodes = new LinkedList<>();
    Queue<Integer> idx = new LinkedList<>();
    nodes.add(root);
    idx.add(0);

    while (!nodes.isEmpty()) {
        int size = nodes.size();
        int first = 0, last = 0;

        for (int i = 0; i < size; i++) {
            TreeNode n = nodes.poll();
            int j = idx.poll();

            if (i == 0) {
                first = j;          // anchor of this level
            }
            j -= first;             // NOTE: re-base to 0 -> prevents overflow
            last = j;

            if (n.left != null) {
                nodes.add(n.left);
                idx.add(2 * j);
            }
            if (n.right != null) {
                nodes.add(n.right);
                idx.add(2 * j + 1);
            }
        }
        res = Math.max(res, last + 1);   // last - 0 + 1
    }
    return res;
}

# python
# LC 662 - Maximum Width of Binary Tree
# IDEA: BFS with (node, heap_index); width = last_idx - first_idx + 1
class Solution:
    def widthOfBinaryTree(self, root):
        # time = O(N), space = O(W)
        if not root:
            return 0
        res = 0
        q = collections.deque([(root, 0)])

        while q:
            size = len(q)
            first = last = 0
            for i in range(size):
                node, j = q.popleft()
                if i == 0:
                    first = j          # anchor of this level
                j -= first             # re-base to 0 (keeps ints small)
                last = j
                if node.left:
                    q.append((node.left, 2 * j))
                if node.right:
                    q.append((node.right, 2 * j + 1))
            res = max(res, last + 1)
        return res

// 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<>();
    q.add(root);
    boolean seenNull = false;

    while (!q.isEmpty()) {
        TreeNode n = q.poll();
        if (n == null) {
            seenNull = true;          // a hole appeared
        } else {
            if (seenNull) {
                return false;         // real node AFTER a hole -> not complete
            }
            q.add(n.left);            // push nulls on purpose
            q.add(n.right);
        }
    }
    return true;
}

# python
# LC 958 - Check Completeness of a Binary Tree
class Solution:
    def isCompleteTree(self, root):
        # time = O(N), space = O(W)
        q = collections.deque([root])
        seen_null = False
        while q:
            node = q.popleft()
            if not node:
                seen_null = True
            else:
                if seen_null:
                    return False      # non-null after a null -> not complete
                q.append(node.left)   # push nulls on purpose
                q.append(node.right)
        return True

# python
# LC 105. Construct Binary Tree from Preorder and Inorder Traversal
# V0
# IDEA : BST property
class Solution(object):
    def buildTree(self, preorder, inorder):
        if len(preorder) == 0:
            return None
        if len(preorder) == 1:
            return TreeNode(preorder[0])
        ### NOTE : init root like below (via TreeNode and root value (preorder[0]))
        root = TreeNode(preorder[0])
        """
        NOTE !!!
        -> # we get index of root.val from "INORDER" to SPLIT TREE
        """
        index = inorder.index(root.val)  # the index of root at inorder, and we can also get the length of left-sub-tree, right-sub-tree ( preorder[1:index+1]) for following using
        # recursion for root.left
        #### NOTE : the idx is from "INORDER"
        #### NOTE : WE idx from inorder in preorder as well 
        #### NOTE : preorder[1 : index + 1] (for left sub tree)
        root.left = self.buildTree(preorder[1 : index + 1], inorder[ : index]) ### since the BST is symmery so the length of left-sub-tree is same in both Preorder and Inorder, so we can use the index to get the left-sub-tree of Preorder as well
        # recursion for root.right 
        root.right = self.buildTree(preorder[index + 1 : ], inorder[index + 1 :]) ### since the BST is symmery so the length of left-sub-tree is same in both Preorder and Inorder, so we can use the index to get the right-sub-tree of Preorder as well
        return root

# python
# LC 106 Construct Binary Tree from Inorder and Postorder Traversal
# V0
# IDEA : Binary Tree property, same as LC 105 
class Solution(object):
    def buildTree(self, inorder, postorder):
        if not inorder:
            return None
        if len(inorder) == 1:
            return TreeNode(inorder[0])
        ### NOTE : we get root from postorder
        root = TreeNode(postorder[-1])
        """
        ### NOTE : the index is from inorder
        ### NOTE : we get index of root in inorder
        #    -> and this idx CAN BE USED IN BOTH inorder, postorder (Binary Tree property)
        """
        idx = inorder.index(root.val)
        ### NOTE : inorder[:idx], postorder[:idx]
        root.left = self.buildTree(inorder[:idx], postorder[:idx])
        ### NOTE : postorder[idx:-1]
        root.right =  self.buildTree(inorder[idx+1:], postorder[idx:-1])
        return root

# LC 257 Binary Tree Paths

# V0
# IDEA : BFS
class Solution:
    def binaryTreePaths(self, root):
        res = []
        ### NOTE : we set q like this : [[root, cur]]
        cur = ""
        q = [[root, cur]]
        while q:
            for i in range(len(q)):
                node, cur = q.pop(0)
                ### NOTE : if node exist, but no sub tree (i.e. not root.left and not root.right)
                #         -> append cur to result
                if node:
                    if not node.left and not node.right:
                        res.append(cur + str(node.val))
                ### NOTE : we keep cur to left sub tree
                if node.left:
                    q.append((node.left, cur + str(node.val) + '->'))
                ### NOTE : we keep cur to left sub tree
                if node.right:
                    q.append((node.right, cur + str(node.val) + '->'))
        return res

# V0'
# IDEA : DFS 
class Solution:
    def binaryTreePaths(self, root):
        ans = []
        def dfs(r, tmp):
            if r.left:
                dfs(r.left, tmp + [str(r.left.val)])
            if r.right:
                dfs(r.right, tmp + [str(r.right.val)])
            if not r.left and not r.right:
                ans.append('->'.join(tmp))
        if not root:
            return []
        dfs(root, [str(root.val)])
        return ans

# LC 298 Binary Tree Longest Consecutive Sequence
# V0
# IDEA : DFS
class Solution(object):
    def longestConsecutive(self, root):
        if not root:
            return 0

        self.result = 0
        self.helper(root, 1)

        return self.result

    def helper(self, root, curLen):
        self.result = curLen if curLen > self.result else self.result
        if root.left:
            if root.left.val == root.val + 1:
                self.helper(root.left, curLen + 1)
            else:
                self.helper(root.left, 1)
        if root.right:
            if root.right.val == root.val + 1:
                self.helper(root.right, curLen + 1)
            else:
                self.helper(root.right, 1)

# V0'
# IDEA : BFS
class Solution(object):
    def longestConsecutive(self, root):
        if root is None:
            return 0

        stack = list()
        stack.append((root, 1))
        maxLen = 1
        while len(stack) > 0:
            node, pathLen = stack.pop()
            if node.left is not None:
                if node.val + 1 == node.left.val:
                    stack.append((node.left, pathLen + 1))
                    maxLen = max(maxLen, pathLen + 1)
                else:
                    stack.append((node.left, 1))
            if node.right is not None:
                if node.val + 1 == node.right.val:
                    stack.append((node.right, pathLen + 1))
                    maxLen = max(maxLen, pathLen + 1)
                else:
                    stack.append((node.right, 1))

        return maxLen

# LC 173. Binary Search Tree Iterator

# V0
# IDEA : STACK + tree
class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = []
        self.inOrder(root)

    def inOrder(self, root):
        if not root:
            return
        self.inOrder(root.right)
        self.stack.append(root.val)
        self.inOrder(root.left)

    def hasNext(self):
        """
        :rtype: bool
        """
        return len(self.stack) > 0

    def next(self):
        """
        :rtype: int
        """
        return self.stack.pop()

// LC 222. Count Complete Tree Nodes
// Java Implementation

// V0 - BFS Approach
// IDEA: Level-order traversal to count all nodes
/**
 * time = O(N)
 * space = O(N)
 */
public int countNodes_BFS(TreeNode root) {
    if (root == null) {
        return 0;
    }

    List<TreeNode> collected = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        collected.add(cur);

        if (cur.left != null) {
            q.add(cur.left);
        }
        if (cur.right != null) {
            q.add(cur.right);
        }
    }

    return collected.size();
}

// V1 - DFS Approach
// IDEA: Recursively count nodes in left and right subtrees
/**
 * time = O(N)
 * space = O(log N)
 */
public int countNodes_DFS(TreeNode root) {
    if (root == null) {
        return 0;
    }

    // Recursively count the nodes in the left subtree
    int leftCount = countNodes_DFS(root.left);

    // Recursively count the nodes in the right subtree
    int rightCount = countNodes_DFS(root.right);

    // Return the total count (current node + left subtree + right subtree)
    return 1 + leftCount + rightCount;
}

// V2 - Optimized Binary Search Approach for Complete Binary Tree
// IDEA: Use complete tree property + binary search on height
/**
 * time = O(log²N)
 * space = O(log N)
 *
 * Key Insight:
 * - In a complete binary tree, at least one subtree is a perfect binary tree
 * - For perfect binary tree with height h: nodes = 2^h - 1
 * - Check left and right subtree heights to determine which is perfect
 */
public int countNodes_Optimized(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);

    if (leftHeight == rightHeight) {
        // Left subtree is perfect binary tree
        // Nodes in left = 2^leftHeight - 1, plus root = 2^leftHeight
        return (1 << leftHeight) + countNodes_Optimized(root.right);
    } else {
        // Right subtree is perfect binary tree
        // Height = rightHeight, nodes = 2^rightHeight - 1, plus root = 2^rightHeight
        return (1 << rightHeight) + countNodes_Optimized(root.left);
    }
}

/**
 * Helper: Get height by traversing left path only
 * Works because in complete tree, leftmost path gives height
 */
private int getHeight(TreeNode node) {
    int height = 0;
    while (node != null) {
        height++;
        node = node.left;
    }
    return height;
}

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 Universal Template 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 = []