Topic 7: Trees

Canonical Question Types #

Basic Traversals (DFS & BFS) #

Recursive and iterative traversals: preorder, inorder, postorder, level order

Problems #

Classic stuff

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

   # M1: recursive
   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution:
       def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

           def traverse(root):
               if not root:
                   return []
               res = []
               res.append(root.val)
               if root.left:
                  res.extend(traverse(root.left))
               if root.right:
                  res.extend(traverse(root.right))

               return res
           return traverse(root)


   # here's the iterative version:
   def iterative_preorder(root):
       if not root:
           return
       stack = [root]
       while stack:
           node = stack.pop()
           print(node.val)  # Preorder position: process node before children

           # Push right first so left is processed first from the stack
           if node.right:
               stack.append(node.right)
           if node.left:
               stack.append(node.left)

Inorder Traversal (94)

The iterative version just needs to left-bias as much as possible.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

   # M1: iterative solution (a little more complex)
   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution:
       def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
           if not root:
               return []

           stack = []
           res = []
           curr = root
           while stack or curr:
               while curr:
                   stack.append(curr)
                   curr = curr.left

               curr = stack.pop()
               res.append(curr.val)
               curr = curr.right

           return res

   # M2: recursive solution:
   class Solution:
       def recursive_inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
           def traverse(root):
               res = []
               if not root:
                   return []

               return traverse(root.left) + [root.val] + traverse(root.right)

           return traverse(root)

Postorder Traversal (145)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
   class Solution:
       def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
           def traverse(root):
               """
               Traverse helper function is easy to implement, just controlling the order of operations gives us the different types of traversals.
               """
               res = []
               if not root:
                   return []

               return traverse(root.left) + traverse(root.right) + [root.val]

           return traverse(root)


   def iterative_postorder(root):
       if not root:
           return
       stack = [root]
       result = []
       while stack:
           node = stack.pop()
           # we gather results in reversed order (parent > left > right) so that we can eventually reverse it and get (right -> left -> parent), which is the post-order.
           result.append(node.val)
           if node.left:
               stack.append(node.left)
           if node.right:
               stack.append(node.right)
               # Reverse to get Left-Right-Root order
       for val in reversed(result):
           print(val)

Level Order Traversal (102)

Here, we directly build the final list, when there’s a new level we enter, we init the [] at the end too. Here we avoid building intermediate lists and build things directly!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    class Solution:
        def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
            if not root:
                return []
            levels = []
            queue = deque([(root, 0)])  # Start at level 0

            while queue:
                node, level = queue.popleft()
                if len(levels) == level:
                    levels.append([])
                levels[level].append(node.val)
                if node.left:
                    queue.append((node.left, level + 1))
                if node.right:
                    queue.append((node.right, level + 1))
            return levels

Here’s a state-threaded recursive dfs version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    class Solution:
        def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
            levels = []
            def dfs(node, level):
                if not node:
                    return
                if len(levels) == level:
                    levels.append([])
                levels[level].append(node.val)
                dfs(node.left, level + 1)
                dfs(node.right, level + 1)
            if root:
                dfs(root, 0)
            return levels

Binary Tree Right Side View (199)

Key idea here is that we can just BFS and take last or do a right-biased DFS:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
    # M1: BFS, TAKE LAST ELEMENT
    from collections import deque
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
            if not root:
                return []

            queue = deque([root])
            res = []
            while queue:
                last = queue[-1]
                res.append(last.val)
                for _ in range(len(queue)):
                    node = queue.popleft()

                    if node.left:
                        queue.append(node.left)

                    if node.right:
                        queue.append(node.right)

            return res

    # M2: ITERATIVE RIGHT-BIASED DFS
    class Solution:
        def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
            if not root:
                return []
            res = []
            stack = [(root, 0)]  # (node, depth)
            while stack:
                node, depth = stack.pop()
                if node:
                    if depth == len(res):
                        res.append(node.val)
                    # Push left first so right is processed first ==> right-bias
                    stack.append((node.left, depth + 1))
                    stack.append((node.right, depth + 1))
            return res

    # M3: RECURSIVE RIGHT BIASED DFS:
    class Solution:
        def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
            res = []
            def dfs(node, depth):
                if not node:
                    return
                if depth == len(res):
                    res.append(node.val)
                dfs(node.right, depth + 1)
                dfs(node.left, depth + 1)
            dfs(root, 0)
            return res

Depth, Height, & Diameter Computation #

Compute tree statistics such as max depth, height, or tree diameter using DFS

Problems #

Maximum Depth (104)

Just a classic level-based traversal, we can choose either BFS or DFS here (just augment the tuple in the stack to keep depth info), I prefer BFS.

In these tree-statistics as usual, it’s a matter of augmenting the tree nodes / using tuples to keep intermediate information that would help us.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
    # M1: BFS solution (iterative)
    from collections import deque

    class Solution:
        def maxDepth(self, root: Optional[TreeNode]) -> int:
            if not root:
                return 0
            queue = deque([root])
            depth = 0

            while queue:
                # for all parents (each level), find their children:
                for _ in range(len(queue)):
                    node = queue.popleft()
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)

                depth += 1

            return depth

    # M2: Iterative DFS solution:
    class Solution:
        def maxDepth(self, root: Optional[TreeNode]) -> int:
            if not root:
                return 0

            stack = [(root, 1)]
            max_depth = 0

            while stack:
                node, depth = stack.pop()
                max_depth = max(max_depth, depth)

                if node.left:
                    stack.append((node.left, depth + 1))
                if node.right:
                    stack.append((node.right, depth + 1))

            return max_depth

Diameter of Binary Tree (543) We have to know the children’s heights before we can compute a node’s diameter, so it’s a post-order processing that we’re doing (children first then parent). The stack can be explicit (iterative DFS) or implicit (recursive call stack).

For the recursive function, I think it’s cleaner

For the iterative DFS version, we store the heights indexed by the node object directly so that we can compute when we need that node.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
    # M1: RECURSIVE SOLUTION:
    class Solution:
        def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
            max_diameter = 0

            # returns the max height for that node
            def traverse(root: Optional[TreeNode]):
                nonlocal max_diameter
                if root is None:
                    return 0
                # max height left
                max_left = traverse(root.left)
                # max height right
                max_right = traverse(root.right)
                combined = max_left + max_right
                # compare with the global accumulator
                max_diameter = max(max_diameter, combined)

                # returns the max height of either choices with an extra edge here
                return max(max_left, max_right) + 1

            traverse(root)

            return max_diameter

    # ITERATIVE SOLUTION:
    class Solution:
        def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
            if not root:
                return 0

            stack = []
            heights = dict()  # node -> height
            max_diameter = 0
            node = root
            last_visited = None

            while stack or node:
                # Go as left as possible
                if node:
                    stack.append(node)
                    node = node.left
                else:
                    peek = stack[-1]
                    # If right child exists and not yet processed
                    if peek.right and last_visited != peek.right:
                        node = peek.right
                    else:
                        # Both children processed, now process node itself
                        left_height = heights.get(peek.left, 0)
                        right_height = heights.get(peek.right, 0)
                        heights[peek] = 1 + max(left_height, right_height)
                        max_diameter = max(max_diameter, left_height + right_height)
                        last_visited = stack.pop()
                        node = None  # Don't go down left again

            return max_diameter

Balanced Binary Tree (110)

Being balanced is about having a height diff tolerance of 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    # Recursive Post-Order DFS with State Threading
    class Solution:
        def isBalanced(self, root: Optional[TreeNode]) -> bool:
            def check(node):
                if not node:
                    return True, 0
                left_balanced, left_height = check(node.left)
                right_balanced, right_height = check(node.right)

                # introspect, then early returns:
                if not left_balanced or not right_balanced:
                    return False, 0

                # introspect against height diff threshold of 1, then early returns:
                if abs(left_height - right_height) > 1:
                    return False, 0

                return True, 1 + max(left_height, right_height)

            return check(root)[0]

Lowest Common Ancestor (LCA) & Ancestor Queries #

Find LCA in binary tree or BST
- for BST, we have the luxury of an ordering that we can exploit
- for a generic binary tree, we’d have to resort to tree-walks regardless
Ancestor path-related questions

Problems #

Lowest Common Ancestor of a Binary Search Tree (235)

As usual, recursive or iterative is up to us, the rough idea, we have to exploit the properties of the BST properly here. We are actually just searching for the split point.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    # ITERATIVE SOLUTION
    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            """
            We're searching for the node in which the two fork out, and we do a root-to-intermediate node walk for this.
            """
            curr = root
            while curr:
                if p.val < curr.val and q.val < curr.val:
                    curr = curr.left
                elif p.val > curr.val and q.val > curr.val:
                    curr = curr.right
                else:
                    return curr
    # RECURSIVE SOLUTION:
    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            if p.val < root.val and q.val < root.val:
                return self.lowestCommonAncestor(root.left, p, q)
            if p.val > root.val and q.val > root.val:
                return self.lowestCommonAncestor(root.right, p, q)
            return root

Lowest Common Ancestor (236)

This question is intentionally there to juxtapose with problem 235. Here we can’t exploit the binary search tree property. Our objective is to chart out root to node then look for the split point.

For the iterative DFS version, we need to preprocess and keep track of parents, then we walk up one of them and then comparatively walk up the other one until we reach it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None

    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            """
            Here we need to do a node to root walk of sorts, so we'd need to encode the child to parent directionality.
            We shall do this without modifying the original class for treenode by just using a simple dict.
            """
            # trivial early returns
            if not root:
                return None

            stack = [(root, None)] # node, parent
            node_to_parent = {root: None} # maps node to parent, this allows us to keep in the parent data.

            # find both p and q:
            while p not in node_to_parent or q not in node_to_parent:
                node, parent = stack.pop()
                node_to_parent[node] = parent
                if node.left:
                    stack.append((node.left, node))

                if node.right:
                    stack.append((node.right, node))

            # now with preprocessed info, we get ancestors:
            ancestors = set()
            while p:
                ancestors.add(p)
                p = node_to_parent[p]

            # now traverse q, comparatively, which would exit as soon as q is in the ancestor set
            while q not in ancestors:
                q = node_to_parent[q]

            return q

The recursive one is straightforward too, we just have to check things correctly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    #+begin_src python -n
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None

    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            # Base case: if root is None or root matches p or q (either one)
            if not root or root == p or root == q:
                return root

            # Recur for left and right subtrees
            left = self.lowestCommonAncestor(root.left, p, q)
            right = self.lowestCommonAncestor(root.right, p, q)

            # If both left and right are non-null, this is the LCA
            if left and right:
                return root

            # Otherwise return the non-null child (either left or right)
            return left if left else right

Binary Search Tree (BST) Properties #

The key idea here is that we can exploit invariants that BSTs have in terms of ordering of nodes and all that.
Validate BSTs, find kth smallest, insert/delete nodes

Problems #

Validate BST (98)

we can’t just be concerned about the local nodes and check left vs right with respect to a particular parent node; it’s an accumulation of the whole range, influenced from the root itself!

This means that we’d have to keep track of range (low, high) for each branch that we’re looking into. It’s fine for us to just do a BFS and keep this range within the tuple statistics

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    # HERE'S THE ITERATIVE SOLUTION
    from collections import deque
    class Solution:
        def isValidBST(self, root: Optional[TreeNode]) -> bool:
            """
            Here, we carry out a simple BFS, keeping track of the cover-range. We've chosen to use exclusive ranges in the range values below.
            """
            queue = deque([(root, -float('inf'), float('inf'))]) # node, lower and upper
            while queue:
                # exclusive bounds
                node, lower, upper = queue.popleft()

                if not node:
                    continue

                if not(lower < node.val < upper):
                    return False

                if node.left:
                    # constricts left, so new upper = node.val
                    queue.append((node.left, lower, node.val))
                if node.right:
                    # constricts right, so new lower = node.val
                    queue.append((node.right, node.val, upper))

            return True
    # HERE'S THE RECURSIVE SOLUTION
    class Solution:
        def isValidBST(self, root: Optional[TreeNode]) -> bool:
            def validate(node, lower, upper):
                if not node:
                    return True

                if not (lower < node.val < upper):
                    return False

                return (validate(node.left, lower, node.val) and
                        validate(node.right, node.val, upper))

            return validate(root, float('-inf'), float('inf'))

Kth Smallest Element in BST (230)

It’s clearly an inorder traversal because inorder BST traversal gives a sorted order, which we then just use the counter variable to determine which is the one:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
    # OPTIMAL, ITERATIVE DFS
    class Solution:
        def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
            stack = [root]
            curr = root
            while stack or curr:
                # go as left as possible, keep adding to the stack:
                while curr:
                    stack.append(curr)
                    curr = curr.left

                # process node, get from the stack:
                curr = stack.pop()
                k -= 1

                if k == 0:
                    return curr.val

                # go right subtree
                curr = curr.right

    # RECURSIVE DFS;
    class Solution:
        def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
            self.k = k
            self.res = None

            def inorder(node):
                if not node or self.res is not None:
                    return

                # left recurse
                inorder(node.left)

                # handle this node
                self.k -= 1
                if self.k == 0:
                    self.res = node.val
                    return

                # handle right
                inorder(node.right)

            inorder(root)

            return self.res

Subtree of Another Tree (572)

We have to just keep the subroot, traverse the OG tree and eventually check if we have the same root as the subroot.

The solution below works in \(O(n * m)\) time, which will work based on the input constraints.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
   # BFS APPROACH:
    from collections import deque
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
            if not root and not subRoot:
                return True

            if not root or not subRoot:
                return False

            def is_same(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
                if not p and not q:
                    return True
                if not p or not q:
                    return False
                if p.val != q.val:
                    return False

                return is_same(p.left, q.left) and is_same(p.right, q.right)

            queue = deque([root])
            while queue:
                node = queue.popleft()
                same = is_same(node, subRoot)
                if same:
                    return True
                else:
                    left, right = node.left, node.right
                    if left:
                        queue.append(left)
                    if right:
                        queue.append(right)

            return False

    # RECURSIVE BFS APPROACH
    class Solution:
        def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
            if not root:
                return False
            if self.is_same(root, subRoot):
                return True
            return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

        def is_same(self, p, q):
            if not p and not q:
                return True
            if not p or not q:
                return False
            if p.val != q.val:
                return False
            return self.is_same(p.left, q.left) and self.is_same(p.right, q.right)

Tree Construction & Serialization #

Construct trees from traversal arrays, using the implicit properties that traversals give
Serialize and deserialize trees for storage/transmission

Problems #

😈 Serialize and Deserialize Binary Tree (297) We can do this by properly having level-order traversals, which we can also prune by removing all the trailing nulls. For the deserialisation, since it is inorder, we can just “walk it level by level” since it’s representing a BFS.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None

    from collections import deque

    class Codec:

        def serialize(self, root):
            """Encodes a tree to a single string.

            :type root: TreeNode
            :rtype: str
            """
            if not root:
                return "null"

            result = []
            queue = deque([root])
            while queue:
                node = queue.popleft()
                if node:
                    result.append(str(node.val))
                    queue.append(node.left)
                    queue.append(node.right)
                else:
                    result.append("null")

            # trim trailing nulls (on the final result), help to reduce size since trailing nulls unncessary
            while result and result[-1] == "null":
                result.pop()

            return ",".join(result)

        def deserialize(self, data):
            """Decodes your encoded data to tree.

            :type data: str
            :rtype: TreeNode
            """
            if data == "null":
                return None

            nodes = data.split(",")
            root = TreeNode(int(nodes[0]))
            queue = deque([root])
            idx = 1
            while queue:
                node = queue.popleft()
                # handle left branch if non-null
                if idx < len(nodes):
                    if nodes[idx] != "null":
                        node.left = TreeNode(int(nodes[idx]))
                        queue.append(node.left)
                    idx += 1

                # handle right branch if non-null
                if idx < len(nodes):
                    if nodes[idx] != "null":
                        node.right = TreeNode(int(nodes[idx]))
                        queue.append(node.right)
                    idx += 1

            return root

⭐️ Construct Binary Tree from Traversals (105)

here we need to exploit the following properties:

for inorder traversal, we can keep partitioning left and right parts of the array to get left and right sub-trees!

The key insight is that the preorder sequence gives you the root, and the inorder sequence tells you how to split the tree. Recursively applying this builds the tree efficiently.

Even better, we can use generators to make things efficient.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
              # M1: STANDARD APPROACH
              class Solution:
                  def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
                      idx_map = {val: i for i, val in enumerate(inorder)}
                      preorder_index = 0

                      def helper(left, right):
                          nonlocal preorder_index
                          if left > right:
                              return None

                          root_val = preorder[preorder_index]
                          preorder_index += 1
                          root = TreeNode(root_val)

                          # Build left and right subtrees
                          root.left = helper(left, idx_map[root_val] - 1)
                          root.right = helper(idx_map[root_val] + 1, right)
                          return root

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

              # M2: USING GENERATORS
              class Solution:
                  def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
                      inorder_val_to_idx = {val: idx for idx, val in enumerate(inorder)}
                      preorder_iter = iter(preorder)  # Create a generator from preorder

                      def helper(left, right):
                          if left > right:
                              return None

                          root_val = next(preorder_iter)  # Get the next root value from the generator
                          root = TreeNode(root_val)
                          inorder_idx = inorder_val_to_idx[root_val]
                          root.left = helper(left, inorder_idx - 1)
                          root.right = helper(inorder_idx + 1, right)

                          return root

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

Path Sum & Root-to-Leaf Problems #

Compute or find root-to-leaf path sums or paths satisfying conditions

Problems #

Path Sum (112)

It’s really just a depth-focused traversal, here I just did it as a pre-ordered traversal. I notice that in these questions, building up from requirements is a good way to make sure that the logic is clear and there are no unnecessary hiccups when implementing things.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = vkl
   #         self.left = left
   #         self.right = right
   class Solution:
       def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
           if not root:
               return False

           stack = [(root, root.val)]
           while stack:
               node, curr_sum = stack.pop()
               if not node.left and not node.right and curr_sum == targetSum:
                   return True

               if node.left:
                   stack.append((node.left, curr_sum + node.left.val))
               if node.right:
                   stack.append((node.right, curr_sum + node.right.val))

           return False

Path Sum II (113)

This is a simple extension that requires us to keep note of the paths that are created. Yet again, the desire to just get it working without falling into deviations because of micro-optimisations helped.

For example, in the accumulation below, we could have kept the state accumulation leaner (e.g. by keeping path of nodes then formatting as a final step to give us the value-based paths) but it wasn’t necessary, the non-optimised version is already globally superior.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   class Solution:
       def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
           """
           We wish to have a depth-focused traversal and we shall accumulate the paths for it.
           A path is a list of node values.
           """
           if not root:
               return []

           stack = [(root, root.val, [root.val])] # curr_node, curr_sum, path
           paths = []
           while stack:
               node, curr_sum, path = stack.pop()

               if not node.left and not node.right and curr_sum == targetSum:
                   paths.append(path)

               if node.left:
                   stack.append((node.left, node.left.val + curr_sum, path + [node.left.val]))
               if node.right:
                   stack.append((node.right, node.right.val + curr_sum, path + [node.right.val]))

           return paths

⭐️😈 Binary Tree Maximum Path Sum(124)

We have to keep track of gain as we do DFS (post-order). We just need to keep accumulating max upward gain, as though we’re walking back up from leaf to root. Here’s a state-threaded version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

   class Solution:
       def maxPathSum(self, root: Optional['TreeNode']) -> int:
           """
           We choose to do a recursive dfs here, which the intent of accumulating max path_sum so far. We acknowledge that it's any (partial) path, doesn't have to be a root-to-leaf path.
           """

           def dfs(node: Optional['TreeNode'], current_max: int) -> Tuple[int, int]:
               """
               We shall return  (max_gain_upwards, max_path_sum_so_far) from this helper.

               For determining the gain, there's a need to pick the best of (left_branch, right_branch) since they are mutually exclusive choices.
               """
               if not node:
                   return (
                       0, # no max gain upwards
                       current_max # path sum so far is current max unchanged.
                   )

               left_gain, current_max = dfs(node.left, current_max)
               right_gain, current_max = dfs(node.right, current_max)

               left_gain = max(left_gain, 0) # here we choose to either include or exclude (and use 0)
               right_gain = max(right_gain, 0)

               price_newpath = node.val + left_gain + right_gain
               current_max = max(current_max, price_newpath)

               # here, a choice has to be made on whether to pick left or right branch.
               max_gain_upwards = node.val + max(left_gain, right_gain)

               return max_gain_upwards, current_max

           _, max_sum = dfs(root, float('-inf'))

           return max_sum

    # FOR DEMO: HERE'S AN ITERATIVE VERSION (super complex though):
    from typing import Optional

    class Solution:
        def maxPathSum(self, root: Optional['TreeNode']) -> int:
            if not root:
                return 0

            stack = []
            gains = {}  # Map node -> max gain upwards
            max_sum = float('-inf')
            last_visited = None
            node = root

            while stack or node:
                if node:
                    stack.append(node)
                    node = node.left
                else:
                    peek_node = stack[-1]
                    # If right child of the recently visited node exists and not processed yet, process right subtree first
                    if peek_node.right and last_visited != peek_node.right:
                        node = peek_node.right
                    else:
                        # Post-order processing:
                        stack.pop()
                        # Get left and right gains, ceiling-ed by 0
                        left_gain = max(gains.get(peek_node.left, 0), 0)
                        right_gain = max(gains.get(peek_node.right, 0), 0)

                        # Price of new path split at this node
                        current_path_sum = peek_node.val + left_gain + right_gain
                        max_sum = max(max_sum, current_path_sum)

                        # Max gain returning to parent
                        gains[peek_node] = peek_node.val + max(left_gain, right_gain)

                        last_visited = peek_node

            return max_sum

Count Good Nodes in Binary Tree (1448)

this is a path traversal with some parent tracking, it’s going to apply for all the levels, so we can just do level order traversal (BFS) and get the job done:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    from collections import deque

    class Solution:
        def goodNodes(self, root: TreeNode) -> int:
            queue = deque([(root, root.val)])
            count = 0
            while queue:
                node, max_above = queue.popleft()
                if node.val >= max_above:
                    count += 1
                max_new = max(max_above, node.val)
                if node.left:
                    queue.append((node.left, max_new))
                if node.right:
                    queue.append((node.right, max_new))
            return count

However, the canonically optimal solution is to use a DFS (here it’s an iterative pre-order DFS) for this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    class Solution:
        def goodNodes(self, root: TreeNode) -> int:
            if not root:
                return 0

            stack = [(root, root.val)]  # Each entry: (node, max_above)
            count = 0

            while stack:
                node, max_above = stack.pop()
                if node.val >= max_above:
                    count += 1
                max_new = max(max_above, node.val)
                # Push children with updated max_above
                if node.left:
                    stack.append((node.left, max_new))
                if node.right:
                    stack.append((node.right, max_new))

            return count

Tree Transformations & Flattening #

Modify tree structure, flatten trees to linked list representations

Problems #

TODO Flatten Binary Tree to Linked List (114)

SOE #

FORGETTING TO EXPLOIT THE PROPERTIS OF A BST!!! (it’s already ordered bro)
Null or empty tree edge cases
Infinite recursion or missing base condition
Forgetting to track visited nodes for graphs/trees that can have cycles
MIXING UP root to leaf path from leaf to root path.
- note that following parent pointer usually ends up creating leaf to root path, hence we might need to reverse it.
Having the wrong mental model:
- height is about edge counting, not about counting nodes / vertices
Incorrect traversal order or index misalignment
Previous Misconceptions:
1. Not every DAG is a tree, a DAG is a superset of a tree. Therefore, to do things like tree-validity checks, we can’t do Kahn’s algo topo-sorting and all that.

Decision Flow #

Need traversal?
- Use DFS (recursive/preorder/inorder/postorder or iterative) or BFS (level-order).
  - BFS: For level-by-level processing, shortest path in unweighted trees.
  - Recursive DFS: Simple for most cases (call stack manages state naturally).
  - Iterative DFS/BFS: Use stacks or queues.
  - Side note: For iterative postorder, use either reversal trick (no visited tracking) or one-stack with `last_visited` for true child-completion semantics.
When to use visited/last_visited tracking?
- Needed for iterative postorder (true left-right-root, no reversal buffer) to guarantee child-to-parent order.
- Required for any graph/tree traversal with possible cycles (general graphs) to prevent revisiting.
- Use parent-tracking for reconstructing ancestry/path information, e.g., for LCA or path queries.
Tree construction or serialization?
- Use level-order traversal (BFS) for serialization/deserialization as with Leetcode 297.
- Recursive divide and conquer for tree construction from traversals (e.g., build tree from inorder & preorder/postorder).
Query path sums or conditions?
- DFS with state tracking (either as args or via return values).
- Example: Accumulate max gain or sum along path, propagate partial results upwards.
Validate BST?
- Inorder traversal (check for sorted order).
- Use explicit min/max value constraints during traversal.
Lowest Common Ancestor (LCA) queries?
- Recursive “found in left/right” checking with backtracking, or use BFS/DFS to record parent pointers for fast ancestor checks.
Which iterative traversal to use?
- Simple result? → Use reversal trick for postorder.
- Need true postorder decision points? → Use last_visited/visited tracking.
- Need to reconstruct path? → Maintain parent pointers during traversal.

Tips #

Only reverse results (reversal trick) for postorder if you don’t need strict post-traversal processing.
For genuine postorder-dependent logic, use last_visited tracking to ensure both children are processed.
Use BFS for problems where processing by levels (depth) matters or the shortest path in unweighted trees is desired.
For graphs, always use a visited set to avoid cycles/infinite loops.

Styles, Tricks, Boilerplates #

Styles #

Tree Property Tricks #

Traversal Properties that we can exploit:
- Ability to reconstruct tree: You can reconstruct a tree from preorder + inorder, or postorder + inorder, but not from preorder + postorder alone (unless the tree is full).
- Partitioning Properties:
  - Preorder Traversal
    - The first element is always the root of the current subtree.
  - Inorder Traversal
    - The index of the root splits the array into left and right subtrees.
  - Postorder Traversal
When they ask extension questions e.g. in the problem “Kth Smallest Element in a BST”, our first reach should try to augment trees into order-statistic trees.
Only after that should we consider things like auxiliary datastructures like a minHeap or whatsoever.

Use state threading #

It’s more efficient to keep state as part of the function parameters or return values.

State threading is a technique where you pass state explicitly through function arguments, which can lead to better performance (stack allocation, cache locality), safer code (no globals), and easier reasoning (pure functions). It is especially intuitive and beneficial in recursive algorithms, dynamic programming, functional programming, and parsing.

Build the final list directly to avoid intermediate list #

See the “level order traversal problem (102)”

Boilerplates #

Tree Traversal #

Here’s the level-order traversal (BFS) implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import deque

def bfs(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val)  # Process the node
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# augmenting statistics would look like this:
def level_order_with_depth(root):
    if not root:
        return
    queue = deque()
    queue.append((root, 1))  # (node, depth)
    while queue:
        node, depth = queue.popleft()
        print(f"depth = {depth}, val = {node.val}")  # or collect in a result list
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

Here’s DFS traversals for easy comparison:

Preorder traversal:

iterative preorder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
      def iterative_preorder(root):
          if not root:
              return
          stack = [root]
          while stack:
              node = stack.pop()
              print(node.val)  # Preorder position: process node before children
              # Push right first so left is processed first
              if node.right:
                  stack.append(node.right)
              if node.left:
                  stack.append(node.left)

      # Parent path tracing: we can keep track of child to parent directionality by using a map

recursive preorder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
      def recursive_preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
          def traverse(root):
             if not root:
                  return []
              res = []
              res.append(root.val)
              if root.left:
                  res.extend(traverse(root.left))
              if root.right:
                  res.extend(traverse(root.right))
               return res
          return traverse(root)

Postorder traversal:

iterative postorder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
      def iterative_postorder(root):
          if not root:
              return
          stack = [root]
          result = []
          while stack:
              node = stack.pop()
              # we gather results in reversed order (parent > left > right) so that we can eventually reverse it and get (right -> left -> parent), which is the post-order.
              result.append(node.val)
              if node.left:
                  stack.append(node.left)
              if node.right:
                  stack.append(node.right)
                  # Reverse to get Left-Right-Root order
          for val in reversed(result):
              print(val)

recursive postorder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
      class Solution:
          def recursivePostorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
              def traverse(root):
                  """
                  Traverse helper function is easy to implement, just controlling the order of operations gives us the different types of traversals.
                  """
                  res = []
                  if not root:
                      return []

                  return traverse(root.left) + traverse(root.right) + [root.val]

              return traverse(root)

Inorder Traversal:

iterative inorder

There are two major iterative postorder approaches:

Visited/ last_visited Tracking: For genuine postorder (processing node after both children), use a stack and a pointer to track the last node visited or a “visited” flag.

This is necessary if side effects or computation must occur immediately after both children, not just up-front in a simple reversed collection.

In the case of binary trees, we can just keep it as a single variable. For general graphs, a collection of visited nodes (e.g. a visited set) would be better.

More context:

Purpose of the last visited tracking:

in “node-after-all-children” traversals), it’s ambiguous when popping from the stack whether you’re processing a node for the first time (on the way down) or if it’s ready to process (on the way back up)
Iterative preorder/inorder don’t generally need a visited check—they either process on the way down (preorder) or on encounter (inorder).
Postorder wants left, then right, then parent.
Since a stack can pop a parent before its right child is handled, you need to know:
1. Did I just process this node’s left/right subtree, and thus is it safe to process the parent now?
2. last_visited helps you remember the last node that was returned/processed. \(\implies\) tracks when a subtree is finished so that we don’t prematurely process a parent node.
This approach might make sense for a general case of “children before node” traversals

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
         def iterative_postorder_with_last_visited(root):
             if not root:
                 return
             stack, result = [], []
             last_visited = None
             curr = root
             while stack or curr:
                 if curr:
                     stack.append(curr)
                     curr = curr.left
                 else:
                     peek = stack[-1]
                     # Only traverse right child if it wasn't just visited
                     if peek.right and last_visited != peek.right:
                         curr = peek.right
                     else:
                         result.append(peek.val)
                         last_visited = stack.pop()
             return result

Reversal Trick: Push nodes in (root, right, left), then reverse the output for true postorder. This avoids the need for visited tracking but only works if you can buffer and reverse results at the end.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
   # reach the leftmode node first:
   def iterative_inorder(root):
       """
       We desire the left => parent => right order. So we keep exploring the left branch as much as possible.
       """
       stack = []
       curr = root
       while stack or curr:
           while curr: # keep entering the left branch.
               # manage left first, keep growing the left:
               stack.append(curr)
               curr = curr.left
               curr = stack.pop()
               print(curr.val)  # Inorder position: process node after left subtree
               curr = curr.right

recursive inorder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
   class Solution:
       def recursive_inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
           def traverse(root):
               res = []
               if not root:
                   return []

               return traverse(root.left) + [root.val] + traverse(root.right)

           return traverse(root)

Right-biased traversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
   def dfs_iterative_right_biased(root):
       """
       The result will be in parent -> right -> left here
       """
       if not root:
           return []

       stack = [root]
       result = []

       while stack:
           node = stack.pop()
           result.append(node.val)

           # Push left child first so right child is popped first (right bias)
           if node.left:
               stack.append(node.left)
           if node.right:
               stack.append(node.right)

       return result

Tree Traversal Order Gives Inspiration for Quick/Merge Sort #

“quicksort is just the preorder traversal of a binary tree, and mergesort is the postorder traversal”

A template for quicksort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
  def sort(nums: List[int], lo: int, hi: int):
      if lo >= hi:
          return
      # ****** pre-order position ******
      # partition the nums[lo..hi], put nums[p] in the right position
      # such that nums[lo..p-1] <= nums[p] < nums[p+1..hi]
      p = partition(nums, lo, hi)

      # recursively partition the left and right subarrays
      sort(nums, lo, p - 1)
      sort(nums, p + 1, hi)

First, build the partition point, then solve the left and right subarrays. Isn’t this just a preorder traversal of a binary tree

A template for mergesort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
  # definition: sort the array nums[lo..hi]
  def sort(nums: List[int], lo: int, hi: int) -> None:
      if lo == hi:
          return
      mid = (lo + hi) // 2
      # Using the definition, sort the array nums[lo..mid]
      sort(nums, lo, mid)
      # Using the definition, sort the array nums[mid+1..hi]
      sort(nums, mid + 1, hi)

      # ****** Post-order position ******
      # At this point, the two subarrays have been sorted
      # Merge the two sorted arrays to make nums[lo..hi] sorted
      merge(nums, lo, mid, hi)

First sort the left and right subarrays, then merge them (similar to merging two sorted linked lists). This is the postorder traversal of a binary tree. Also, this is what we call divide and conquer — that’s all.

TODO KIV #

[ ] Existing canonicals #

Tree transformations and flattenning 1) TODO Flatten Binary Tree to Linked List (114)

[ ] Possible New additions (extra) #

Key Problems from Leetcode (Worth adding to your track)
- Binary Tree Zigzag Level Order Traversal (103)
- Path Sum III (437)
- Sum of Left Leaves (404)
- Serialize and Deserialize N-ary Tree (428)
- Construct Binary Tree from Postorder and Inorder (106)
- Lowest Common Ancestor of a Tree (Offline Tarjan algorithm - not on Leetcode but classical)
- Count Univalue Subtrees (250)
- Range Sum BST (938)

[ ] Island Problem Family #

see solve all island problems with dfs