Skip to content

16. Tree#

Problems at a glance#

LC Problem
94 Binary Tree Inorder Traversal ↗
144 Binary Tree Preorder Traversal ↗
145 Binary Tree Postorder Traversal ↗
102 Binary Tree Level Order Traversal ↗
103 Binary Tree Zigzag Level Order Traversal ↗
107 Binary Tree Level Order Traversal II ↗
987 Vertical Order Traversal of a Binary Tree ↗
226 Invert Binary Tree ↗
563 Binary Tree Tilt ↗
543 Diameter of Binary Tree ↗
617 Merge Two Binary Trees ↗
111 Minimum Depth of Binary Tree ↗
110 Balanced Binary Tree ↗
104 Maximum Depth of Binary Tree ↗
100 Same Tree ↗
101 Symmetric Tree ↗
700 Search in a Binary Search Tree ↗
653 Two Sum IV - Input is a BST ↗
530 Minimum Absolute Difference in BST ↗
938 Range Sum of BST ↗
450 Delete Node in a BST ↗
669 Trim a Binary Search Tree ↗
701 Insert into a Binary Search Tree ↗
230 Kth Smallest Element in a BST ↗
1305 All Elements in Two Binary Search Trees ↗
173 Binary Search Tree Iterator ↗
1038 Binary Search Tree to Greater Sum Tree ↗
1373 Maximum Sum BST in Binary Tree ↗
257 Binary Tree Paths ↗
112 Path Sum ↗
113 Path Sum II ↗
129 Sum Root to Leaf Numbers ↗
124 Binary Tree Maximum Path Sum ↗
437 Path Sum III ↗
1457 Pseudo-Palindromic Paths in a Binary Tree ↗
105 Construct Binary Tree from Preorder and Inorder Traversal ↗
106 Construct Binary Tree from Inorder and Postorder Traversal ↗
889 Construct Binary Tree from Preorder and Postorder Traversal ↗
108 Convert Sorted Array to Binary Search Tree ↗
1008 Construct Binary Search Tree from Preorder Traversal ↗
199 Binary Tree Right Side View ↗
236 Lowest Common Ancestor of a Binary Tree ↗
235 Lowest Common Ancestor of a Binary Search Tree ↗
1123 Lowest Common Ancestor of Deepest Leaves ↗
1361 Validate Binary Tree Nodes ↗
98 Validate Binary Search Tree ↗
114 Flatten Binary Tree to Linked List ↗
222 Count Complete Tree Nodes ↗
662 Maximum Width of Binary Tree ↗
958 Check Completeness of a Binary Tree ↗
993 Cousins in Binary Tree ↗
1026 Maximum Difference Between Node and Ancestor ↗
1530 Number of Good Leaf Nodes Pairs ↗
865 Smallest Subtree with all the Deepest Nodes ↗
863 All Nodes Distance K in Binary Tree ↗
1379 Find a Corresponding Node of a Binary Tree in a Clone of That Tree ↗
894 All Possible Full Binary Trees ↗
1325 Delete Leaves With a Given Value ↗
1110 Delete Nodes And Return Forest ↗
652 Find Duplicate Subtrees ↗
337 House Robber III ↗
2096 Step-By-Step Directions From a Binary Tree Node to Another ↗
117 Populating Next Right Pointers in Each Node II ↗
979 Distribute Coins in Binary Tree ↗
297 Serialize and Deserialize Binary Tree ↗
968 Binary Tree Cameras ↗

Traversal#

Problem 1: Binary Tree Inorder Traversal (Leetcode:94)#

Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:

Example 3:

Input: root = []
Output: []

Example 4:

Input: root = [1]
Output: [1]

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)

        dfs(root)
        return result
Explanation:

  1. Inorder order: left subtree → node → right subtree.
  2. Recursive DFS: Visit left, append current value, then visit right.
  3. Base case: empty node returns immediately.

Time: O(n)  |  Space: O(h) recursion stack

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result, stack = [], []
        curr = root

        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            result.append(curr.val)
            curr = curr.right

        return result
Explanation:

  1. Simulate recursion with an explicit stack.
  2. Push all left children first; pop, record value, then move to right child.
  3. Repeat until both stack and current pointer are empty.

Time: O(n)  |  Space: O(h)

Problem 2: Binary Tree Preorder Traversal (Leetcode:144)#

Problem Statement

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]
Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Explanation:

Example 3:

Input: root = []
Output: []

Example 4:

Input: root = [1]
Output: [1]

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def dfs(node):
            if not node:
                return
            result.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return result
Explanation:

  1. Preorder order: node → left subtree → right subtree.
  2. Recursive DFS: Append value first, then recurse left and right.
  3. Base case: empty node returns immediately.

Time: O(n)  |  Space: O(h) recursion stack

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result, stack = [], [root]

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

        return result
Explanation:

  1. Push root onto a stack; process nodes in LIFO order.
  2. Pop, record value, then push right before left so left is processed first.
  3. Mirrors recursive preorder without call stack overhead.

Time: O(n)  |  Space: O(h)

Problem 3: Binary Tree Postorder Traversal (Leetcode:145)#

Problem Statement

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]
Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,6,7,5,2,9,8,3,1]
Explanation:

Example 3:

Input: root = []
Output: []

Example 4:

Input: root = [1]
Output: [1]

Constraints:

  • The number of the nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            dfs(node.right)
            result.append(node.val)

        dfs(root)
        return result
Explanation:

  1. Postorder order: left subtree → right subtree → node.
  2. Recursive DFS: Recurse left and right before appending the current value.
  3. Base case: empty node returns immediately.

Time: O(n)  |  Space: O(h) recursion stack

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack1, stack2 = [root], []

        while stack1:
            node = stack1.pop()
            stack2.append(node)
            if node.left:
                stack1.append(node.left)
            if node.right:
                stack1.append(node.right)

        return [node.val for node in reversed(stack2)]
Explanation:

  1. Stack 1 processes nodes in modified preorder (root → right → left).
  2. Stack 2 collects popped nodes; reversing gives left → right → root.
  3. Avoids the tricky single-stack postorder simulation.

Time: O(n)  |  Space: O(n)

Problem 4: Binary Tree Level Order Traversal (Leetcode:102)#

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
Code and Explanation 

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

        while queue:
            level = []
            for _ in range(len(queue)):
                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
Explanation:

  1. BFS with a queue processes nodes level by level.
  2. Snapshot len(queue) each iteration to isolate one level.
  3. Enqueue left and right children after recording the current node.

Time: O(n)  |  Space: O(w) where w = max width

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []

        def dfs(node, depth):
            if not node:
                return
            if depth == len(result):
                result.append([])
            result[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return result
Explanation:

  1. DFS tracks depth; extend result when visiting a new level.
  2. Append each node's value to result[depth].
  3. Same output as BFS, useful when already using depth-first logic.

Time: O(n)  |  Space: O(h)

Problem 5: Binary Tree Zigzag Level Order Traversal (Leetcode:103)#

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result, queue, left_to_right = [], deque([root]), True

        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level if left_to_right else level[::-1])
            left_to_right = not left_to_right

        return result
Explanation:

  1. Standard BFS collects each level left to right.
  2. Toggle direction each level — reverse the list on odd-indexed levels.
  3. Enqueue children normally; only the output order alternates.

Time: O(n)  |  Space: O(w)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result, queue, left_to_right = [], deque([root]), True

        while queue:
            level = deque()
            for _ in range(len(queue)):
                node = queue.popleft()
                if left_to_right:
                    level.append(node.val)
                else:
                    level.appendleft(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(list(level))
            left_to_right = not left_to_right

        return result
Explanation:

  1. Build each level in order using append or appendleft on a deque.
  2. Avoids reversing the whole level after collection.
  3. Same BFS structure; only insertion side changes per level.

Time: O(n)  |  Space: O(w)

Problem 6: Binary Tree Level Order Traversal II (Leetcode:107)#

Problem Statement

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
Code and Explanation 

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

        while queue:
            level = []
            for _ in range(len(queue)):
                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[::-1]
Explanation:

  1. Run standard level-order BFS top to bottom.
  2. Reverse the result list to get bottom-up order.
  3. Simple and readable; one extra O(levels) reversal.

Time: O(n)  |  Space: O(w)

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

        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.insert(0, level)

        return result
Explanation:

  1. Same BFS, but insert each completed level at index 0.
  2. Builds bottom-up order during traversal without a final reverse.
  3. insert(0, …) costs O(levels) per level — acceptable for interview clarity.

Time: O(n)  |  Space: O(w)

Problem 7: Vertical Order Traversal of a Binary Tree (Leetcode:987)#

Problem Statement

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.

Example 2:


Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
1 is at the top, so it comes first.
5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.

Example 3:


Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        nodes = []
        queue = deque([(root, 0, 0)])  # node, row, col

        while queue:
            node, row, col = queue.popleft()
            nodes.append((col, row, node.val))
            if node.left:
                queue.append((node.left, row + 1, col - 1))
            if node.right:
                queue.append((node.right, row + 1, col + 1))

        nodes.sort()
        result, prev_col = [], None
        for col, _, val in nodes:
            if col != prev_col:
                result.append([])
                prev_col = col
            result[-1].append(val)

        return result
Explanation:

  1. BFS assigns each node a (row, col) coordinate from the root at (0, 0).
  2. Sort by (col, row, val) — column left-to-right, then top-to-bottom, then value.
  3. Group consecutive equal columns into output lists.

Time: O(n log n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        columns = defaultdict(list)

        def dfs(node, row, col):
            if not node:
                return
            columns[col].append((row, node.val))
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)
        result = []
        for col in sorted(columns):
            columns[col].sort()
            result.append([val for _, val in columns[col]])

        return result
Explanation:

  1. DFS records (row, val) tuples in a map keyed by column index.
  2. Sort columns left to right; within each column sort by row then value.
  3. Equivalent logic to BFS; DFS avoids an explicit queue.

Time: O(n log n)  |  Space: O(n)

Build Understanding#

Problem 1: Invert Binary Tree (Leetcode:226)#

Problem Statement

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Explanation:

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
Explanation:

  1. Swap left and right pointers at the current node.
  2. Recurse on both subtrees to invert the entire tree.
  3. Base case: None needs no swapping.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        queue = deque([root])

        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return root
Explanation:

  1. BFS queue visits every node level by level.
  2. Swap children at each node before enqueueing them.
  3. Avoids recursion depth limits on skewed trees.

Time: O(n)  |  Space: O(w)

Problem 2: Binary Tree Tilt (Leetcode:563)#

Problem Statement

Given the root of a binary tree, return the sum of every tree node's tilt.

The tilt of a node is the absolute difference between the sum of all the left subtree node's values and all of the right subtree node's values. If a node does not exist, then the sum will be zero.

Example 1:

Input: root = [1,2,3]
Output: 1
Explanation:
Tilt of node 1: |2 − 3| = 1.
Tilt of node 2: |0 − 0| = 0.
Tilt of node 3: |0 − 0| = 0.
The sum of every node's tilt is 1.

Example 2:

Input: root = [4,2,9,3,5,null,7]
Output: 15
Explanation:
Tilt of node 4: |11 − 13| = 2.
Tilt of node 9: |0 − 7| = 7.
Tilt of node 5: |3 − 0| = 3.
Tilt of node 7: |0 − 0| = 0.
Tilt of node 2: |3 − 0| = 3.
Tilt of node 3: |0 − 0| = 0.
The sum of every node's tilt is 2 + 7 + 3 + 0 + 3 + 0 = 15.

Constraints:

  • The number of nodes in the tree is in the range [1, 10⁴].
  • 0 <= Node.val <= 200
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        self.tilt = 0

        def subtree_sum(node):
            if not node:
                return 0
            left_sum = subtree_sum(node.left)
            right_sum = subtree_sum(node.right)
            self.tilt += abs(left_sum - right_sum)
            return node.val + left_sum + right_sum

        subtree_sum(root)
        return self.tilt
Explanation:

  1. Postorder DFS computes each subtree's sum bottom-up.
  2. At each node, add |left_sum − right_sum| to the global tilt.
  3. Return node.val + left_sum + right_sum to the parent.

Time: O(n)  |  Space: O(h)

 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 findTilt(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        stack, sums, tilt, last = [(root, False)], {}, 0, None

        while stack:
            node, visited = stack[-1]
            if visited or (not node.left and not node.right):
                stack.pop()
                left_sum = sums.get(node.left, 0)
                right_sum = sums.get(node.right, 0)
                tilt += abs(left_sum - right_sum)
                sums[node] = node.val + left_sum + right_sum
                last = node
            elif node.right and node.right is not last:
                stack.append((node.right, False))
            elif node.left:
                stack.append((node.left, False))
            else:
                stack[-1] = (node, True)

        return tilt
Explanation:

  1. Explicit postorder stack with a visited flag tracks processing order.
  2. Store subtree sums in a hash map; accumulate tilt when a node is finalized.
  3. Same logic as recursion without call-stack depth concerns.

Time: O(n)  |  Space: O(n)

Problem 3: Diameter of Binary Tree (Leetcode:543)#

Problem Statement

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [1, 10⁴].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0

        def height(node):
            if not node:
                return 0
            left_h = height(node.left)
            right_h = height(node.right)
            self.diameter = max(self.diameter, left_h + right_h)
            return 1 + max(left_h, right_h)

        height(root)
        return self.diameter
Explanation:

  1. Diameter at a node = longest path through it = left_height + right_height.
  2. Postorder height DFS updates global max while returning subtree height.
  3. Count edges, not nodes — heights exclude the current node.

Time: O(n)  |  Space: O(h)

 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        stack, heights, diameter, last = [(root, False)], {}, 0, None

        while stack:
            node, visited = stack[-1]
            if visited or (not node.left and not node.right):
                stack.pop()
                left_h = heights.get(node.left, 0)
                right_h = heights.get(node.right, 0)
                diameter = max(diameter, left_h + right_h)
                heights[node] = 1 + max(left_h, right_h)
                last = node
            elif node.right and node.right is not last:
                stack.append((node.right, False))
            elif node.left:
                stack.append((node.left, False))
            else:
                stack[-1] = (node, True)

        return diameter
Explanation:

  1. Simulate postorder to compute heights bottom-up without recursion.
  2. Update diameter whenever a node's left and right heights are known.
  3. Useful when recursion depth is a concern on very tall trees.

Time: O(n)  |  Space: O(n)

Problem 4: Merge Two Binary Trees (Leetcode:617)#

Problem Statement

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the non-null node will be used as the node of the new tree.

Return the merged tree.

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

Constraints:

  • The number of nodes in both trees is in the range [0, 2000].
  • -10⁴ <= Node.val <= 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1
Explanation:

  1. If one tree is empty, return the other as the merged subtree.
  2. Sum values at overlapping nodes and recurse on both children.
  3. Reuse root1 in place to avoid extra node allocation.

Time: O(min(m, n))  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        stack = [(root1, root2)]

        while stack:
            n1, n2 = stack.pop()
            n1.val += n2.val
            if n1.left and n2.left:
                stack.append((n1.left, n2.left))
            elif n2.left:
                n1.left = n2.left
            if n1.right and n2.right:
                stack.append((n1.right, n2.right))
            elif n2.right:
                n1.right = n2.right

        return root1
Explanation:

  1. Stack pairs of corresponding nodes from both trees.
  2. Sum values; push both children when both exist, otherwise attach the non-null child.
  3. Same merge logic as recursion in iterative form.

Time: O(min(m, n))  |  Space: O(h)

Problem 5: Minimum Depth of Binary Tree (Leetcode:111)#

Problem Statement

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints:

  • The number of nodes in the tree is in the range [0, 10⁵].
  • -1000 <= Node.val <= 1000
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        if not root.left:
            return 1 + self.minDepth(root.right)
        if not root.right:
            return 1 + self.minDepth(root.left)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
Explanation:

  1. Minimum depth = shortest root-to-leaf path (must reach a leaf).
  2. If one child is missing, follow the non-null side — a single-child node is not a leaf.
  3. Both children present: 1 + min(left, right).

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue = deque([(root, 1)])

        while queue:
            node, depth = queue.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))
Explanation:

  1. BFS finds the shallowest node first — ideal for minimum depth.
  2. Return immediately when a leaf (no children) is dequeued.
  3. Avoids traversing deeper levels once the first leaf is found.

Time: O(n)  |  Space: O(w)

Problem 6: Balanced Binary Tree (Leetcode:110)#

Problem Statement

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than one.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: The left subtree of node 1 has a depth of 3, while the right subtree has a depth of 1.

Example 3:

Input: root = []
Output: true

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -10⁴ <= Node.val <= 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node):
            if not node:
                return 0
            left_h = height(node.left)
            if left_h == -1:
                return -1
            right_h = height(node.right)
            if right_h == -1:
                return -1
            if abs(left_h - right_h) > 1:
                return -1
            return 1 + max(left_h, right_h)

        return height(root) != -1
Explanation:

  1. Balanced iff every node's subtrees differ in height by at most 1.
  2. Return −1 as a sentinel when imbalance is detected; propagate up immediately.
  3. Single DFS pass computes height and checks balance together — O(n), not O(n²).

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        stack, heights, last = [(root, False)], {}, None

        while stack:
            node, visited = stack[-1]
            if visited or (not node.left and not node.right):
                stack.pop()
                left_h = heights.get(node.left, 0)
                right_h = heights.get(node.right, 0)
                if abs(left_h - right_h) > 1:
                    return False
                heights[node] = 1 + max(left_h, right_h)
                last = node
            elif node.right and node.right is not last:
                stack.append((node.right, False))
            elif node.left:
                stack.append((node.left, False))
            else:
                stack[-1] = (node, True)

        return True
Explanation:

  1. Postorder iteration computes subtree heights bottom-up.
  2. Check balance at each node when both child heights are known.
  3. Return False immediately on the first imbalance.

Time: O(n)  |  Space: O(n)

Problem 7: Maximum Depth of Binary Tree (Leetcode:104)#

Problem Statement

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

  • The number of nodes in the tree is in the range [0, 10⁴].
  • -100 <= Node.val <= 100
Code and Explanation 

1
2
3
4
5
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
Explanation:

  1. Depth of a node = 1 + max depth of its subtrees.
  2. Base case: empty tree has depth 0.
  3. Classic divide-and-conquer on left and right children.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        depth, queue = 0, deque([root])

        while queue:
            depth += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return depth
Explanation:

  1. BFS processes one level per outer loop iteration.
  2. Increment depth after draining the current level's queue snapshot.
  3. Count levels rather than recursing — natural for level-wise thinking.

Time: O(n)  |  Space: O(w)

Problem 8: Same Tree (Leetcode:100)#

Problem Statement

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -10⁴ <= Node.val <= 10⁴
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Explanation:

  1. Both null → trees match at this branch.
  2. One null or different values → not the same tree.
  3. Recurse on both left and right pairs.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        queue = deque([(p, q)])

        while queue:
            n1, n2 = queue.popleft()
            if not n1 and not n2:
                continue
            if not n1 or not n2 or n1.val != n2.val:
                return False
            queue.append((n1.left, n2.left))
            queue.append((n1.right, n2.right))

        return True
Explanation:

  1. BFS queue holds pairs of nodes to compare simultaneously.
  2. Mismatch on structure or value → return False immediately.
  3. Enqueue both child pairs for continued comparison.

Time: O(n)  |  Space: O(w)

Problem 9: Symmetric Tree (Leetcode:101)#

Problem Statement

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror(left, right):
            if not left and not right:
                return True
            if not left or not right or left.val != right.val:
                return False
            return mirror(left.left, right.right) and mirror(left.right, right.left)

        return not root or mirror(root.left, root.right)
Explanation:

  1. Mirror check: compare left.left with right.right and left.right with right.left.
  2. Both subtrees must be mirrors at every level.
  3. Empty tree is symmetric by definition.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        queue = deque([(root.left, root.right)])

        while queue:
            left, right = queue.popleft()
            if not left and not right:
                continue
            if not left or not right or left.val != right.val:
                return False
            queue.append((left.left, right.right))
            queue.append((left.right, right.left))

        return True
Explanation:

  1. Queue pairs of mirror-position nodes from left and right subtrees.
  2. Enqueue outer pair (left.left, right.right) and inner pair (left.right, right.left).
  3. Same mirror logic as recursion without call-stack depth.

Time: O(n)  |  Space: O(w)

Binary Search Trees#

Problem 1: Search in a Binary Search Tree (Leetcode:700)#

Problem Statement

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
Explanation: Subtree rooted at node with value 2.

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

Constraints:

  • The number of nodes in the tree is in the range [1, 5000].
  • 1 <= Node.val <= 10⁷
  • root is a valid binary search tree.
  • 1 <= val <= 10⁷
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return root
        if val < root.val:
            return self.searchBST(root.left, val)
        return self.searchBST(root.right, val)
Explanation:

  1. BST property: All values in the left subtree are smaller; all in the right are larger.
  2. Base case: Return the node when found, or None when the subtree is empty.
  3. Recurse left if val is smaller, otherwise right.

Time: O(h)  |  Space: O(h)

1
2
3
4
5
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root and root.val != val:
            root = root.left if val < root.val else root.right
        return root
Explanation:

  1. Walk from root following the BST ordering rule at each step.
  2. Stop when the target is found or the current pointer becomes None.
  3. No recursion — constant auxiliary space aside from the pointer.

Time: O(h)  |  Space: O(1)

Problem 2: Two Sum IV - Input is a BST (Leetcode:653)#

Problem Statement

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k. Otherwise, return false.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Constraints:

  • The number of nodes in the tree is in the range [1, 10⁴].
  • -10⁴ <= Node.val <= 10⁴
  • root is a valid binary search tree.
  • -10⁵ <= k <= 10⁵
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        seen = set()

        def dfs(node):
            if not node:
                return False
            if k - node.val in seen:
                return True
            seen.add(node.val)
            return dfs(node.left) or dfs(node.right)

        return dfs(root)
Explanation:

  1. DFS the tree and store every visited value in a hash set.
  2. Before inserting, check whether k - node.val was seen already.
  3. Short-circuit on the first matching pair.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        vals = []

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            vals.append(node.val)
            inorder(node.right)

        inorder(root)
        lo, hi = 0, len(vals) - 1
        while lo < hi:
            total = vals[lo] + vals[hi]
            if total == k:
                return True
            if total < k:
                lo += 1
            else:
                hi -= 1
        return False
Explanation:

  1. Inorder traversal of a BST yields a sorted array.
  2. Run the classic two-pointer scan on that sorted list.
  3. Uses BST ordering explicitly instead of a hash set.

Time: O(n)  |  Space: O(n)

Problem 3: Minimum Absolute Difference in BST (Leetcode:530)#

Problem Statement

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]
Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 10⁴].
  • 0 <= Node.val <= 10⁵
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        self.prev = None
        self.ans = float("inf")

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            if self.prev is not None:
                self.ans = min(self.ans, node.val - self.prev)
            self.prev = node.val
            inorder(node.right)

        inorder(root)
        return self.ans
Explanation:

  1. Inorder visits nodes in sorted order in a BST.
  2. Track the previous value and update the minimum adjacent gap.
  3. The answer is the smallest difference between consecutive inorder values.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        stack, prev, ans = [], None, float("inf")
        curr = root

        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            if prev is not None:
                ans = min(ans, curr.val - prev)
            prev = curr.val
            curr = curr.right

        return ans
Explanation:

  1. Simulate recursive inorder with an explicit stack.
  2. Each time a node is popped, compare it with the previous visited value.
  3. Same logic as the recursive version without call-stack overhead.

Time: O(n)  |  Space: O(h)

Problem 4: Range Sum of BST (Leetcode:938)#

Problem Statement

Given the root of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

Constraints:

  • The number of nodes in the tree is in the range [1, 2 × 10⁴].
  • 1 <= Node.val <= 10⁵
  • 1 <= low <= high <= 10⁵
  • All Node.val are unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        return (
            root.val
            + self.rangeSumBST(root.left, low, high)
            + self.rangeSumBST(root.right, low, high)
        )
Explanation:

  1. Prune branches that cannot contain values in [low, high].
  2. If the current value is inside the range, include it and search both subtrees.
  3. BST ordering avoids visiting entire subtrees that are out of range.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        stack, total = [root], 0
        while stack:
            node = stack.pop()
            if not node:
                continue
            if node.val < low:
                stack.append(node.right)
            elif node.val > high:
                stack.append(node.left)
            else:
                total += node.val
                stack.append(node.left)
                stack.append(node.right)
        return total
Explanation:

  1. Explicit stack replaces recursion while keeping the same pruning rules.
  2. Only nodes inside the range contribute to the running sum.
  3. Skipped subtrees are never pushed onto the stack.

Time: O(n)  |  Space: O(h)

Problem 5: Delete Node in a BST (Leetcode:450)#

Problem Statement

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the value that was in the node key before deletion should take on the value of its in-order predecessor or successor. Then, the node with key should be deleted.

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value 0.

Example 3:

Input: root = [5,3,6,2,4,null,7], key = 7
Output: [5,3,6,2,4]

Constraints:

  • The number of nodes in the tree is in the range [0, 10⁴].
  • -10⁵ <= Node.val <= 10⁵
  • Each node has a unique value.
  • root is a valid binary search tree.
  • -10⁵ <= key <= 10⁵
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            succ = root.right
            while succ.left:
                succ = succ.left
            root.val = succ.val
            root.right = self.deleteNode(root.right, succ.val)
        return root
Explanation:

  1. Search for the target using BST ordering.
  2. 0/1 child: splice the node out by returning its non-null child.
  3. Two children: copy the inorder successor value, then delete that successor from the right subtree.

Time: O(h)  |  Space: O(h)

 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
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        dummy = TreeNode(0, root)
        parent, curr = dummy, root
        while curr and curr.val != key:
            parent = curr
            curr = curr.left if key < curr.val else curr.right
        if not curr:
            return dummy.left

        if not curr.left:
            child = curr.right
        elif not curr.right:
            child = curr.left
        else:
            succ_parent, succ = curr, curr.right
            while succ.left:
                succ_parent, succ = succ, succ.left
            curr.val = succ.val
            if succ_parent.left == succ:
                succ_parent.left = succ.right
            else:
                succ_parent.right = succ.right
            return dummy.left

        if parent.left == curr:
            parent.left = child
        else:
            parent.right = child
        return dummy.left
Explanation:

  1. Dummy node simplifies deleting the root.
  2. Walk down with a parent pointer until the target is found.
  3. Apply the same three deletion cases without recursion.

Time: O(h)  |  Space: O(1)

Problem 6: Trim a Binary Search Tree (Leetcode:669)#

Problem Statement

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain (i.e., any node's descendant should remain a descendant).

Return the new root of the trimmed binary search tree.

Example 1:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

Example 2:

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

Constraints:

  • The number of nodes in the tree is in the range [1, 10⁴].
  • 0 <= Node.val <= 10⁴
  • The value of each node in the tree is unique.
  • 0 <= low <= high <= 10⁴
  • root is a valid binary search tree.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val < low:
            return self.trimBST(root.right, low, high)
        if root.val > high:
            return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root
Explanation:

  1. If the current value is below low, the whole left side is invalid — recurse right.
  2. If above high, recurse left instead.
  3. Otherwise trim both subtrees and keep the current node.

Time: O(n)  |  Space: O(h)

 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 trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        vals = []

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            if low <= node.val <= high:
                vals.append(node.val)
            inorder(node.right)

        def build(lo, hi):
            if lo > hi:
                return None
            mid = (lo + hi) // 2
            node = TreeNode(vals[mid])
            node.left = build(lo, mid - 1)
            node.right = build(mid + 1, hi)
            return node

        inorder(root)
        return build(0, len(vals) - 1)
Explanation:

  1. Collect in-range values via inorder traversal.
  2. Rebuild a balanced BST from the filtered sorted array.
  3. Different trade-off: extra space, but produces a height-balanced result.

Time: O(n)  |  Space: O(n)

Problem 7: Insert into a Binary Search Tree (Leetcode:701)#

Problem Statement

You are given the root node of a binary search tree (BST) and a val to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5,null,null,null,null,null,null,null]
Explanation: Another accepted tree is shown below.

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Constraints:

  • The number of nodes in the tree will be in the range [0, 10⁴].
  • -10⁸ <= Node.val <= 10⁸
  • All the values Node.val are unique.
  • -10⁸ <= val <= 10⁸
  • It's guaranteed that val does not exist in the original BST.
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
        return root
Explanation:

  1. Empty spot: create a new leaf when root is None.
  2. Go left if val is smaller, otherwise go right.
  3. Return the unchanged subtree root after linking the new node.

Time: O(h)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)
        curr = root
        while True:
            if val < curr.val:
                if not curr.left:
                    curr.left = TreeNode(val)
                    break
                curr = curr.left
            else:
                if not curr.right:
                    curr.right = TreeNode(val)
                    break
                curr = curr.right
        return root
Explanation:

  1. Walk down until the correct empty child slot is found.
  2. Attach the new node directly without recursive calls.
  3. Original root reference is preserved and returned.

Time: O(h)  |  Space: O(1)

Problem 8: Kth Smallest Element in a BST (Leetcode:230)#

Problem Statement

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 10⁴
  • 0 <= Node.val <= 10⁴

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.k = k
        self.ans = 0

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            self.k -= 1
            if self.k == 0:
                self.ans = node.val
                return
            inorder(node.right)

        inorder(root)
        return self.ans
Explanation:

  1. Inorder traversal visits BST nodes from smallest to largest.
  2. Decrement k each time a node is visited.
  3. Stop early once the k-th smallest value is recorded.

Time: O(h + k)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack, curr = [], root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
            curr = curr.right
Explanation:

  1. Standard iterative inorder using a stack.
  2. Count nodes as they are popped in sorted order.
  3. Return immediately when the count reaches k.

Time: O(h + k)  |  Space: O(h)

Problem 9: All Elements in Two Binary Search Trees (Leetcode:1305)#

Problem Statement

Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

  • The number of nodes in each tree is in the range [0, 5000].
  • -10⁵ <= Node.val <= 10⁵
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def getAllElements(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> List[int]:
        def inorder(node, arr):
            if not node:
                return
            inorder(node.left, arr)
            arr.append(node.val)
            inorder(node.right, arr)

        a, b = [], []
        inorder(root1, a)
        inorder(root2, b)
        i = j = 0
        result = []
        while i < len(a) and j < len(b):
            if a[i] <= b[j]:
                result.append(a[i])
                i += 1
            else:
                result.append(b[j])
                j += 1
        result.extend(a[i:])
        result.extend(b[j:])
        return result
Explanation:

  1. Flatten both BSTs to sorted arrays via inorder traversal.
  2. Merge the two sorted arrays with a two-pointer scan.
  3. Simple and easy to reason about.

Time: O(m + n)  |  Space: O(m + n)

 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
class Solution:
    def getAllElements(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> List[int]:
        stack1, stack2 = [], []

        def push_lefts(node, stack):
            while node:
                stack.append(node)
                node = node.left

        def next_val(stack):
            node = stack.pop()
            push_lefts(node.right, stack)
            return node.val

        push_lefts(root1, stack1)
        push_lefts(root2, stack2)
        result = []
        while stack1 and stack2:
            if stack1[-1].val <= stack2[-1].val:
                result.append(next_val(stack1))
            else:
                result.append(next_val(stack2))
        while stack1:
            result.append(next_val(stack1))
        while stack2:
            result.append(next_val(stack2))
        return result
Explanation:

  1. Each stack simulates inorder traversal lazily for one tree.
  2. Compare stack tops and advance the smaller side — like merging linked lists.
  3. Avoids storing full inorder arrays upfront.

Time: O(m + n)  |  Space: O(h1 + h2)

Problem 10: Binary Search Tree Iterator (Leetcode:173)#

Problem Statement

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

  • BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
  • boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
  • int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

Input:
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output: [null, 3, 7, true, 9, true, 13, true, 15, true, 20, false]
Explanation:

Constraints:

  • The number of nodes in the tree is in the range [1, 10⁵].
  • 0 <= Node.val <= 10⁶
  • At most 10⁵ calls will be made to hasNext, and next.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.values = []
        self.index = 0
        stack, curr = [], root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            self.values.append(curr.val)
            curr = curr.right

    def next(self) -> int:
        val = self.values[self.index]
        self.index += 1
        return val

    def hasNext(self) -> bool:
        return self.index < len(self.values)
Explanation:

  1. Precompute the full inorder list during construction.
  2. next() and hasNext() become array index operations.
  3. Fast per-call cost, but O(n) upfront space.

Time: O(n) init, O(1) per call  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self._push_lefts(root)

    def _push_lefts(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        node = self.stack.pop()
        self._push_lefts(node.right)
        return node.val

    def hasNext(self) -> bool:
        return bool(self.stack)
Explanation:

  1. Only materialize the next value when next() is called.
  2. Stack always holds the path to the next smallest unvisited node.
  3. Better space for sparse next() calls on large trees.

Time: O(1) amortized per call  |  Space: O(h)

Problem 11: Binary Search Tree to Greater Sum Tree (Leetcode:1038)#

Problem Statement

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree maintains the following property for every node:

Node.left.val < Node.val < Node.right.val

Return the root of the Greater Tree.

Example 1:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2:

Input: root = [0,null,1]
Output: [1,null,1]

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • 0 <= Node.val <= 100
  • All the values in the tree are unique.

Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.running = 0

        def reverse_inorder(node):
            if not node:
                return
            reverse_inorder(node.right)
            self.running += node.val
            node.val = self.running
            reverse_inorder(node.left)

        reverse_inorder(root)
        return root
Explanation:

  1. Reverse inorder visits nodes from largest to smallest.
  2. Maintain a running sum of all nodes already visited.
  3. Overwrite each node with that cumulative sum.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        stack, curr, running = [], root, 0
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.right
            curr = stack.pop()
            running += curr.val
            curr.val = running
            curr = curr.left
        return root
Explanation:

  1. Push right spine first, then pop and update — reverse inorder with a stack.
  2. Same running-sum logic as the recursive version.
  3. Avoids recursion depth on skewed trees.

Time: O(n)  |  Space: O(h)

Problem 12: Maximum Sum BST in Binary Tree (Leetcode:1373)#

Problem Statement

Given a root of a binary tree, return the maximum sum of all keys in any BST that is also a subtree in the given binary tree.

Example 1:

Input: root = [1,4,3,4,null,5,5]
Output: 20
Explanation: Maximum sum in a valid BST is obtained in the subtree rooted at node 3 with keys 3, 4, and 5.

Example 2:

Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid BST is obtained in the subtree rooted at node 1 with keys 1 and 2.

Example 3:

Input: root = [-4,-2,-5,-1,-3,null,2]
Output: 6
Explanation: Maximum sum in a valid BST is obtained in the subtree rooted at node 2 with key 2.

Constraints:

  • The number of nodes in the tree is in the range [1, 4 × 10⁴].
  • -4 × 10⁴ <= Node.val <= 4 × 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.ans = 0

        def dfs(node):
            if not node:
                return True, float("inf"), float("-inf"), 0
            l_ok, lmin, lmax, lsum = dfs(node.left)
            r_ok, rmin, rmax, rsum = dfs(node.right)
            if l_ok and r_ok and lmax < node.val < rmin:
                total = lsum + rsum + node.val
                self.ans = max(self.ans, total)
                return True, min(lmin, node.val), max(rmax, node.val), total
            return False, 0, 0, 0

        dfs(root)
        return self.ans
Explanation:

  1. Postorder DFS returns whether a subtree is a valid BST plus its min, max, and sum.
  2. If both children are valid BSTs and bounds match, the current subtree is a BST too.
  3. Track the maximum BST sum seen globally.

Time: O(n)  |  Space: O(h)

 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
class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.ans = 0

        def is_bst(node, lo, hi):
            if not node:
                return True, 0
            if not (lo < node.val < hi):
                return False, 0
            left_ok, left_sum = is_bst(node.left, lo, node.val)
            right_ok, right_sum = is_bst(node.right, node.val, hi)
            if left_ok and right_ok:
                return True, left_sum + right_sum + node.val
            return False, 0

        def dfs(node):
            if not node:
                return
            ok, total = is_bst(node, float("-inf"), float("inf"))
            if ok:
                self.ans = max(self.ans, total)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return self.ans
Explanation:

  1. Try every node as the root of a candidate BST subtree.
  2. Validate BST property with min/max bounds and compute subtree sum.
  3. Correct but revisits nodes repeatedly — useful contrast to the linear approach.

Time: O(n²) worst case  |  Space: O(h)

Path#

Problem 1: Binary Tree Paths (Leetcode:257)#

Problem Statement

Given the root of a binary tree, return all root-to-leaf paths in any order**.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Example 2:

Input: root = [1]
Output: ["1"]

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        result = []

        def dfs(node, path):
            if not node:
                return
            path += str(node.val)
            if not node.left and not node.right:
                result.append(path)
                return
            dfs(node.left, path + "->")
            dfs(node.right, path + "->")

        dfs(root, "")
        return result
Explanation:

  1. Build the path string as DFS descends from root to leaf.
  2. At a leaf, append the complete "a->b->c" string to the answer.
  3. Backtracking is implicit via passing updated path strings.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root:
            return []
        result, stack = [], [(root, str(root.val))]
        while stack:
            node, path = stack.pop()
            if not node.left and not node.right:
                result.append(path)
                continue
            if node.right:
                stack.append((node.right, path + "->" + str(node.right.val)))
            if node.left:
                stack.append((node.left, path + "->" + str(node.left.val)))
        return result
Explanation:

  1. Stack stores (node, path_so_far) pairs.
  2. Push children with extended path strings before popping the next state.
  3. Same output as recursive DFS without recursion.

Time: O(n)  |  Space: O(h)

Problem 2: Path Sum (Leetcode:112)#

Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation:
The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation:
There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation:
Since the tree is empty, there are no root-to-leaf paths.

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == targetSum
        remaining = targetSum - root.val
        return self.hasPathSum(root.left, remaining) or self.hasPathSum(root.right, remaining)
Explanation:

  1. Subtract the current value from the remaining target as you descend.
  2. At a leaf, check whether the remaining sum equals zero.
  3. Return true if either subtree yields a valid root-to-leaf path.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        stack = [(root, targetSum - root.val)]
        while stack:
            node, remaining = stack.pop()
            if not node.left and not node.right and remaining == 0:
                return True
            if node.right:
                stack.append((node.right, remaining - node.right.val))
            if node.left:
                stack.append((node.left, remaining - node.left.val))
        return False
Explanation:

  1. Stack entries track remaining sum needed from the current node to a leaf.
  2. Early return when a leaf satisfies remaining == 0.
  3. Equivalent logic to the recursive version.

Time: O(n)  |  Space: O(h)

Problem 3: Path Sum II (Leetcode:113)#

Problem Statement

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation:
There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        result = []

        def dfs(node, remaining, path):
            if not node:
                return
            path.append(node.val)
            if not node.left and not node.right and remaining == node.val:
                result.append(path[:])
            else:
                dfs(node.left, remaining - node.val, path)
                dfs(node.right, remaining - node.val, path)
            path.pop()

        dfs(root, targetSum, [])
        return result
Explanation:

  1. Track the current path in a list while DFS walks the tree.
  2. At a leaf where the remaining sum equals the leaf value, copy the path into the answer.
  3. Backtrack with path.pop() after exploring each branch.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return []
        result, stack = [], [(root, targetSum - root.val, [root.val])]
        while stack:
            node, remaining, path = stack.pop()
            if not node.left and not node.right and remaining == 0:
                result.append(path)
                continue
            if node.right:
                stack.append((node.right, remaining - node.right.val, path + [node.right.val]))
            if node.left:
                stack.append((node.left, remaining - node.left.val, path + [node.left.val]))
        return result
Explanation:

  1. Each stack frame stores the node, remaining sum, and path list so far.
  2. Valid leaf paths are collected when remaining == 0.
  3. Child paths are built by copying and extending the parent path.

Time: O(n)  |  Space: O(h)

Problem 4: Sum Root to Leaf Numbers (Leetcode:129)#

Problem Statement

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, current):
            if not node:
                return 0
            current = current * 10 + node.val
            if not node.left and not node.right:
                return current
            return dfs(node.left, current) + dfs(node.right, current)

        return dfs(root, 0)
Explanation:

  1. Build the number top-down by shifting left (* 10) and adding the digit.
  2. At a leaf, return the completed number.
  3. Sum the leaf numbers from all root-to-leaf paths.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        total = 0
        queue = deque([(root, root.val)])
        while queue:
            node, current = queue.popleft()
            if not node.left and not node.right:
                total += current
                continue
            if node.left:
                queue.append((node.left, current * 10 + node.left.val))
            if node.right:
                queue.append((node.right, current * 10 + node.right.val))
        return total
Explanation:

  1. BFS queue stores (node, number_so_far) pairs.
  2. Extend the running number when enqueueing children.
  3. Add to total whenever a leaf is dequeued.

Time: O(n)  |  Space: O(w)

Problem 5: Binary Tree Maximum Path Sum (Leetcode:124)#

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation:
The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation:
The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

  • The number of nodes in the tree is in the range [1, 3 * 104].
  • -1000 <= Node.val <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.ans = float("-inf")

        def gain(node):
            if not node:
                return 0
            left = max(gain(node.left), 0)
            right = max(gain(node.right), 0)
            self.ans = max(self.ans, node.val + left + right)
            return node.val + max(left, right)

        gain(root)
        return self.ans
Explanation:

  1. gain(node) returns the best downward path sum starting at node (one branch only).
  2. Ignore negative contributions by clamping child gains to zero.
  3. A path through node can use left + node + right; update the global maximum.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        stack, post, visited = [root], [], set()
        while stack:
            node = stack[-1]
            if (node.left and node.left not in visited) or (node.right and node.right not in visited):
                if node.right and node.right not in visited:
                    stack.append(node.right)
                if node.left and node.left not in visited:
                    stack.append(node.left)
            else:
                post.append(stack.pop())
                visited.add(node)

        gain = {None: 0}
        ans = float("-inf")
        for node in post:
            left = max(gain.get(node.left, 0), 0)
            right = max(gain.get(node.right, 0), 0)
            ans = max(ans, node.val + left + right)
            gain[node] = node.val + max(left, right)
        return ans
Explanation:

  1. Build a postorder list iteratively with a visited set.
  2. Process nodes bottom-up, storing each node's best downward gain in a map.
  3. Same recurrence as recursion, but without the call stack.

Time: O(n)  |  Space: O(n)

Problem 6: Path Sum III (Leetcode:437)#

Problem Statement

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation:
The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

Constraints:

  • The number of nodes in the tree is in the range [0, 1000].
  • -109 9
  • -1000 <= targetSum <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        prefix = {0: 1}
        self.count = 0

        def dfs(node, curr):
            if not node:
                return
            curr += node.val
            self.count += prefix.get(curr - targetSum, 0)
            prefix[curr] = prefix.get(curr, 0) + 1
            dfs(node.left, curr)
            dfs(node.right, curr)
            prefix[curr] -= 1
            if prefix[curr] == 0:
                del prefix[curr]

        dfs(root, 0)
        return self.count
Explanation:

  1. Prefix sums along the current root-to-node path are stored in a hash map.
  2. If curr - targetSum exists, a valid downward path ending here was found.
  3. Backtrack prefix counts when returning from a subtree.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def count_from(node, remaining):
            if not node:
                return 0
            total = 1 if node.val == remaining else 0
            total += count_from(node.left, remaining - node.val)
            total += count_from(node.right, remaining - node.val)
            return total

        def dfs(node):
            if not node:
                return 0
            return (
                count_from(node, targetSum)
                + dfs(node.left)
                + dfs(node.right)
            )

        return dfs(root)
Explanation:

  1. For each node, count paths that start there and sum to targetSum.
  2. Recurse into both children to cover all possible start points.
  3. Simple but revisits paths — O(n²) worst case on skewed trees.

Time: O(n²) worst case  |  Space: O(h)

Problem 7: Pseudo-Palindromic Paths in a Binary Tree (Leetcode:1457)#

Problem Statement

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation:
The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation:
The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3:

Input: root = [9]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 1 <= Node.val <= 9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        self.count = 0

        def dfs(node, mask):
            if not node:
                return
            mask ^= 1 << node.val
            if not node.left and not node.right:
                if mask == 0 or (mask & (mask - 1)) == 0:
                    self.count += 1
                return
            dfs(node.left, mask)
            dfs(node.right, mask)

        dfs(root, 0)
        return self.count
Explanation:

  1. Toggle a bit for each digit (1–9) as the path descends.
  2. A path can form a palindrome when at most one digit has odd frequency.
  3. That means the bitmask is 0 or a single power of two.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        self.count = 0

        def dfs(node, freq):
            if not node:
                return
            freq[node.val] += 1
            if not node.left and not node.right:
                odds = sum(v % 2 for v in freq)
                if odds <= 1:
                    self.count += 1
            else:
                dfs(node.left, freq)
                dfs(node.right, freq)
            freq[node.val] -= 1

        dfs(root, [0] * 10)
        return self.count
Explanation:

  1. Track digit counts in a length-10 array (values are 1–9).
  2. At each leaf, count how many digits appear an odd number of times.
  3. Valid when at most one odd count — explicit version of the bitmask check.

Time: O(n)  |  Space: O(h)

construct a binary tree/BST#

Problem 1: Construct Binary Tree from Preorder and Inorder Traversal (Leetcode:105)#

Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values.
  • Each value of inorder also appears in preorder.
  • preorder is guaranteed to be the preorder traversal of the tree.
  • inorder is guaranteed to be the inorder traversal of the tree.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        idx_map = {val: i for i, val in enumerate(inorder)}
        self.pre_idx = 0

        def dfs(left, right):
            if left > right:
                return None
            root_val = preorder[self.pre_idx]
            self.pre_idx += 1
            root = TreeNode(root_val)
            mid = idx_map[root_val]
            root.left = dfs(left, mid - 1)
            root.right = dfs(mid + 1, right)
            return root

        return dfs(0, len(inorder) - 1)
Explanation:

  1. Preorder gives the root; inorder locates the split between left and right subtrees.
  2. Hash map finds the root index in inorder in O(1).
  3. Recurse on [left, mid-1] and [mid+1, right].

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        idx_map = {val: i for i, val in enumerate(inorder)}
        root = TreeNode(preorder[0])
        stack = [root]
        for i in range(1, len(preorder)):
            val = preorder[i]
            node = TreeNode(val)
            if idx_map[val] < idx_map[stack[-1].val]:
                stack[-1].left = node
            else:
                parent = stack[-1]
                while stack and idx_map[val] > idx_map[stack[-1].val]:
                    parent = stack.pop()
                parent.right = node
            stack.append(node)
        return root
Explanation:

  1. Stack tracks the path of nodes whose right child is not yet assigned.
  2. If the next preorder value belongs left of the stack top in inorder, attach as left child.
  3. Otherwise pop until the correct parent is found, then attach as right child.

Time: O(n)  |  Space: O(h)

Problem 2: Construct Binary Tree from Inorder and Postorder Traversal (Leetcode:106)#

Problem Statement

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder and postorder consist of unique values.
  • Each value of postorder also appears in inorder.
  • inorder is guaranteed to be the inorder traversal of the tree.
  • postorder is guaranteed to be the postorder traversal of the tree.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        idx_map = {val: i for i, val in enumerate(inorder)}
        self.post_idx = len(postorder) - 1

        def dfs(left, right):
            if left > right:
                return None
            root_val = postorder[self.post_idx]
            self.post_idx -= 1
            root = TreeNode(root_val)
            mid = idx_map[root_val]
            root.right = dfs(mid + 1, right)
            root.left = dfs(left, mid - 1)
            return root

        return dfs(0, len(inorder) - 1)
Explanation:

  1. Postorder's last element is always the subtree root.
  2. Find that root in inorder to split left/right ranges.
  3. Build right subtree first because postorder is consumed from the end.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not postorder:
            return None
        root = TreeNode(postorder[-1])
        stack = [root]
        in_idx = len(inorder) - 1
        for i in range(len(postorder) - 2, -1, -1):
            val = postorder[i]
            node = TreeNode(val)
            if inorder[in_idx] == val:
                in_idx -= 1
                stack[-1].left = node
            else:
                parent = stack[-1]
                while stack and inorder[in_idx] != stack[-1].val:
                    parent = stack.pop()
                parent.right = node
                in_idx -= 1
            stack.append(node)
        return root
Explanation:

  1. Process postorder from right to left, mirroring the recursive pointer walk.
  2. Stack holds nodes awaiting a left or right assignment.
  3. Compare against inorder from the end to decide attachment side.

Time: O(n)  |  Space: O(h)

Problem 3: Construct Binary Tree from Preorder and Postorder Traversal (Leetcode:889)#

Problem Statement

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]

Constraints:

  • 1 <= preorder.length <= 30
  • 1 <= preorder[i] <= preorder.length
  • All the values of preorder are unique.
  • postorder.length == preorder.length
  • 1 <= postorder[i] <= postorder.length
  • All the values of postorder are unique.
  • It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def constructFromPrePost(self, pre: List[int], post: List[int]) -> Optional[TreeNode]:
        if not pre:
            return None
        root = TreeNode(pre[0])
        if len(pre) == 1:
            return root
        left_root = pre[1]
        split = post.index(left_root) + 1
        root.left = self.constructFromPrePost(pre[1:1 + split], post[:split])
        root.right = self.constructFromPrePost(pre[1 + split:], post[split:-1])
        return root
Explanation:

  1. First preorder value is the root; second preorder value starts the left subtree.
  2. Find that left-root value in postorder — everything before its last occurrence is the left subtree.
  3. Recurse on the left and right slices.

Time: O(n²) worst case  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def constructFromPrePost(self, pre: List[int], post: List[int]) -> Optional[TreeNode]:
        post_idx = {val: i for i, val in enumerate(post)}
        self.pre_idx = 0

        def dfs(pre_lo, pre_hi, post_lo, post_hi):
            if pre_lo > pre_hi:
                return None
            root_val = pre[self.pre_idx]
            self.pre_idx += 1
            root = TreeNode(root_val)
            if pre_lo == pre_hi:
                return root
            left_root = pre[self.pre_idx]
            split = post_idx[left_root]
            left_size = split - post_lo + 1
            root.left = dfs(self.pre_idx, self.pre_idx + left_size - 1, post_lo, split)
            root.right = dfs(self.pre_idx + left_size, pre_hi, split + 1, post_hi - 1)
            return root

        return dfs(0, len(pre) - 1, 0, len(post) - 1)
Explanation:

  1. Index map avoids repeated post.index() scans.
  2. Left subtree size is derived from where the left child appears in postorder.
  3. Same split logic as Approach 1, but O(n) total with pointer-based slicing.

Time: O(n)  |  Space: O(n)

Problem 4: Convert Sorted Array to Binary Search Tree (Leetcode:108)#

Problem Statement

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation:
[0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation:
[1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

  • 1 4
  • -104 4
  • nums is sorted in a strictly increasing order.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def build(lo, hi):
            if lo > hi:
                return None
            mid = (lo + hi) // 2
            root = TreeNode(nums[mid])
            root.left = build(lo, mid - 1)
            root.right = build(mid + 1, hi)
            return root

        return build(0, len(nums) - 1)
Explanation:

  1. Pick the middle element as the root to keep the tree balanced.
  2. Recursively build left half and right half of the array.
  3. Result is a height-balanced BST.

Time: O(n)  |  Space: O(log n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        root = None
        for val in nums:
            root = self._insert(root, val)
        return root

    def _insert(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self._insert(root.left, val)
        else:
            root.right = self._insert(root.right, val)
        return root
Explanation:

  1. Insert each value using standard BST insertion.
  2. Sorted input produces a skewed tree, not a balanced one.
  3. Useful contrast: simpler code, but O(n log n) time and O(n) height worst case.

Time: O(n log n)  |  Space: O(n) worst case

Problem 5: Construct Binary Search Tree from Preorder Traversal (Leetcode:1008)#

Problem Statement

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

Example 1:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Example 2:

Input: preorder = [1,3]
Output: [1,null,3]

Constraints:

  • 1 <= preorder.length <= 100
  • 1 <= preorder[i] <= 1000
  • All the values of preorder are unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        self.idx = 0

        def dfs(bound):
            if self.idx == len(preorder) or preorder[self.idx] > bound:
                return None
            val = preorder[self.idx]
            self.idx += 1
            node = TreeNode(val)
            node.left = dfs(val)
            node.right = dfs(bound)
            return node

        return dfs(float("inf"))
Explanation:

  1. Preorder for a BST visits parent before children; each node has an upper bound from its ancestors.
  2. Build the left child first (values must be < current), then the right child (values < bound).
  3. A single index walks the preorder array once.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        root = TreeNode(preorder[0])
        stack = [root]
        for val in preorder[1:]:
            node = TreeNode(val)
            if val < stack[-1].val:
                stack[-1].left = node
            else:
                parent = stack[-1]
                while stack and val > stack[-1].val:
                    parent = stack.pop()
                parent.right = node
            stack.append(node)
        return root
Explanation:

  1. Stack tracks ancestors whose right child may still be extended.
  2. If the new value is smaller than the top, it belongs in the left subtree.
  3. Otherwise pop until finding the correct parent, then attach as right child.

Time: O(n)  |  Space: O(h)

View Problem#

Problem 1: Binary Tree Right Side View (Leetcode:199)#

Problem Statement

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Example 2:

Example 3:

Example 4:

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result, queue = [], deque([root])

        while queue:
            level_size = len(queue)
            rightmost = None
            for _ in range(level_size):
                node = queue.popleft()
                rightmost = node
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(rightmost.val)

        return result
Explanation:

  1. BFS visits the tree level by level.
  2. The last node processed at each level is the rightmost visible node.
  3. Append its value before moving to the next level.

Time: O(n)  |  Space: O(w)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def dfs(node, depth):
            if not node:
                return
            if depth == len(result):
                result.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return result
Explanation:

  1. Visit right subtree before left so the first node at each depth is rightmost.
  2. When depth == len(result), this depth has not been recorded yet — append the value.
  3. Same output as BFS with a depth-first traversal.

Time: O(n)  |  Space: O(h)

Lowest Common Ancestor#

Problem 1: Lowest Common Ancestor of a Binary Tree (Leetcode:236)#

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation:
The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation:
The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right
Explanation:

  1. Postorder search: recurse left and right; if both return non-null, current node is the LCA.
  2. If only one side finds a target (or an ancestor of a target), bubble that result up.
  3. Base case: None, or hitting p/q directly.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        parent = {root: None}
        stack = [root]

        while p not in parent or q not in parent:
            node = stack.pop()
            if node.left:
                parent[node.left] = node
                stack.append(node.left)
            if node.right:
                parent[node.right] = node
                stack.append(node.right)

        ancestors = set()
        while p:
            ancestors.add(p)
            p = parent[p]

        while q not in ancestors:
            q = parent[q]
        return q
Explanation:

  1. Build a parent map via iterative DFS until both p and q are discovered.
  2. Walk p up to root, storing every ancestor in a set.
  3. Walk q upward until hitting a shared ancestor — that node is the LCA.

Time: O(n)  |  Space: O(n)

Problem 2: Lowest Common Ancestor of a Binary Search Tree (Leetcode:235)#

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation:
The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation:
The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left
            elif p.val > root.val and q.val > root.val:
                root = root.right
            else:
                return root
Explanation:

  1. BST ordering: if both targets are smaller, LCA lies in the left subtree; if both larger, go right.
  2. Otherwise the current node sits between them (or equals one) — it is the LCA.
  3. No full-tree search needed.

Time: O(h)  |  Space: O(1)

1
2
3
4
5
6
7
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
Explanation:

  1. Same BST split logic as the iterative version.
  2. Recurse into the subtree that contains both nodes.
  3. Return the node where paths diverge.

Time: O(h)  |  Space: O(h)

Problem 3: Lowest Common Ancestor of Deepest Leaves (Leetcode:1123)#

Problem Statement

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation:
We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest leaf-nodes of the tree.
Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.

Example 2:

Input: root = [1]
Output: [1]
Explanation:
The root is the deepest node in the tree, and it's the lca of itself.

Example 3:

Input: root = [0,1,3,null,2]
Output: [2]
Explanation:
The deepest leaf node in the tree is 2, the lca of one node is itself.

Constraints:

  • The number of nodes in the tree will be in the range [1, 1000].
  • 0 <= Node.val <= 1000
  • The values of the nodes in the tree are unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node):
            if not node:
                return 0, None
            left_depth, left_lca = dfs(node.left)
            right_depth, right_lca = dfs(node.right)
            if left_depth > right_depth:
                return left_depth + 1, left_lca
            if right_depth > left_depth:
                return right_depth + 1, right_lca
            return left_depth + 1, node

        return dfs(root)[1]
Explanation:

  1. Return (depth, lca_candidate) from each subtree.
  2. If left and right depths differ, propagate the deeper side's LCA upward.
  3. If equal, current node is the LCA of all deepest leaves below it.

Time: O(n)  |  Space: O(h)

 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
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        parent = {root: None}
        queue = deque([(root, 0)])
        deepest, max_depth = [], 0

        while queue:
            node, depth = queue.popleft()
            if depth > max_depth:
                max_depth = depth
                deepest = [node]
            elif depth == max_depth:
                deepest.append(node)
            if node.left:
                parent[node.left] = node
                queue.append((node.left, depth + 1))
            if node.right:
                parent[node.right] = node
                queue.append((node.right, depth + 1))

        def lca(a, b):
            ancestors = set()
            while a:
                ancestors.add(a)
                a = parent[a]
            while b not in ancestors:
                b = parent[b]
            return b

        result = deepest[0]
        for node in deepest[1:]:
            result = lca(result, node)
        return result
Explanation:

  1. BFS finds all deepest leaves and records their depth.
  2. Build a parent map, then pairwise LCA-merge the deepest nodes.
  3. Correct but heavier than the single-pass postorder approach.

Time: O(n)  |  Space: O(n)

Validate Trees#

Problem 1: Validate Binary Tree Nodes (Leetcode:1361)#

Problem Statement

You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Constraints:

  • n == leftChild.length == rightChild.length
  • 1 4
  • -1 <= leftChild[i], rightChild[i] <= n - 1
Code and Explanation 

 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
class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        parent_count = [0] * n
        for child in leftChild + rightChild:
            if child != -1:
                parent_count[child] += 1
                if parent_count[child] > 1:
                    return False

        roots = [i for i in range(n) if parent_count[i] == 0]
        if len(roots) != 1:
            return False
        root = roots[0]

        visited = set()

        def dfs(node):
            if node == -1 or node in visited:
                return
            visited.add(node)
            dfs(leftChild[node])
            dfs(rightChild[node])

        dfs(root)
        return len(visited) == n
Explanation:

  1. A valid binary tree has exactly one root (parent count 0) and every other node has exactly one parent.
  2. Reject immediately if any node has more than one parent.
  3. DFS from the root must visit all n nodes — catches disconnected components and cycles.

Time: O(n)  |  Space: O(n)

 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
class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        parent = [-1] * n
        roots = 0

        def find(x):
            while parent[x] != -1 and parent[x] != x:
                x = parent[x]
            return x

        def union(child, node):
            nonlocal roots
            if child == -1:
                return True
            if parent[child] != -1:
                return False
            if find(child) == find(node):
                return False
            parent[child] = node
            roots -= 1
            return True

        for i in range(n):
            if parent[i] == -1:
                roots += 1
            if not union(leftChild[i], i) or not union(rightChild[i], i):
                return False

        return roots == 1
Explanation:

  1. Track in-degree via parent[]; each node can receive at most one parent edge.
  2. Union-find detects cycles when linking a child already connected to its ancestor.
  3. Valid iff exactly one root remains and no union failed.

Time: O(n α(n))  |  Space: O(n)

Problem 2: Validate Binary Search Tree (Leetcode:98)#

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation:
The root node's value is 5 but its right child's value is 4.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 31 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = float("-inf")

        def inorder(node):
            nonlocal prev
            if not node:
                return True
            if not inorder(node.left):
                return False
            if node.val <= prev:
                return False
            prev = node.val
            return inorder(node.right)

        return inorder(root)
Explanation:

  1. Inorder traversal of a valid BST yields strictly increasing values.
  2. Track prev; reject if node.val <= prev.
  3. Short-circuit on first violation.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, low, high):
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return valid(node.left, low, node.val) and valid(node.right, node.val, high)

        return valid(root, float("-inf"), float("inf"))
Explanation:

  1. Each node must satisfy low < val < high for its valid range.
  2. Left child inherits upper bound node.val; right child inherits lower bound node.val.
  3. Handles duplicate-value edge cases that break naive comparisons.

Time: O(n)  |  Space: O(h)

miscellaneous#

Problem 1: Flatten Binary Tree to Linked List (Leetcode:114)#

Problem Statement

Given the root of a binary tree, flatten the tree into a "linked list":

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return
        stack = []
        curr = root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.right
            curr = stack.pop()
            if curr.left:
                stack.append(curr.left)
            if stack:
                curr.right = stack[-1]
                curr.left = None
Explanation:

  1. Process nodes in root → right → left order (reverse of desired preorder tail).
  2. Link each processed node to the next stack top as its right child.
  3. Clears left pointers to form the linked-list structure.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        self.prev = None

        def dfs(node):
            if not node:
                return
            dfs(node.right)
            dfs(node.left)
            node.right = self.prev
            node.left = None
            self.prev = node

        dfs(root)
Explanation:

  1. Reverse postorder (right, left, node) visits nodes from tail to head of the target list.
  2. Attach current node in front of prev via node.right = prev.
  3. Classic O(h) space recursive variant.

Time: O(n)  |  Space: O(h)

Problem 2: Count Complete Tree Nodes (Leetcode:222)#

Problem Statement

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [0, 5 * 104].
  • 0 4
  • The tree is guaranteed to be complete.
Code and Explanation 

1
2
3
4
5
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
Explanation:

  1. Straightforward recursion counts every node.
  2. Works on any tree shape; ignores the complete-tree property.
  3. Simple baseline solution.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        def left_height(node):
            h = 0
            while node:
                h += 1
                node = node.left
            return h

        if not root:
            return 0
        left_h = left_height(root.left)
        right_h = left_height(root.right)

        if left_h == right_h:
            return (1 << left_h) + self.countNodes(root.right)
        return (1 << right_h) + self.countNodes(root.left)
Explanation:

  1. Compare left and right spine heights from the root's children.
  2. Equal heights → left subtree is a perfect tree of 2^left_h nodes; recurse only on the right.
  3. Unequal → right subtree is perfect; recurse on the left. Exploits completeness for O(log² n).

Time: O(log² n)  |  Space: O(log n)

Problem 3: Maximum Width of Binary Tree (Leetcode:662)#

Problem Statement

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation:
The maximum width exists in the third level with length 4 (5,3,null,9).

Example 2:

Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation:
The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3:

Input: root = [1,3,2,5]
Output: 2
Explanation:
The maximum width exists in the second level with length 2 (3,2).

Constraints:

  • The number of nodes in the tree is in the range [1, 3000].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        max_width = 0
        queue = deque([(root, 0)])

        while queue:
            level_size = len(queue)
            _, first_idx = queue[0]
            _, last_idx = queue[-1]
            max_width = max(max_width, last_idx - first_idx + 1)

            for _ in range(level_size):
                node, idx = queue.popleft()
                if node.left:
                    queue.append((node.left, 2 * idx))
                if node.right:
                    queue.append((node.right, 2 * idx + 1))

        return max_width
Explanation:

  1. Assign each node an index as in a heap array: left 2*i, right 2*i+1.
  2. Width at a level = last_index - first_index + 1.
  3. BFS processes level by level, tracking the maximum width.

Time: O(n)  |  Space: O(w)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_width = 0
        leftmost = {}

        def dfs(node, depth, idx):
            if not node:
                return
            if depth not in leftmost:
                leftmost[depth] = idx
            self.max_width = max(self.max_width, idx - leftmost[depth] + 1)
            dfs(node.left, depth + 1, 2 * idx)
            dfs(node.right, depth + 1, 2 * idx + 1)

        dfs(root, 0, 0)
        return self.max_width
Explanation:

  1. DFS tracks the leftmost index seen at each depth.
  2. Current width at depth d = idx - leftmost[d] + 1.
  3. Same indexing scheme as BFS without a queue.

Time: O(n)  |  Space: O(h)

Problem 4: Check Completeness of a Binary Tree (Leetcode:958)#

Problem Statement

Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation:
Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation:
The node with value 7 isn't as far left as possible.

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • 1 <= Node.val <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        queue = deque([root])
        seen_null = False

        while queue:
            node = queue.popleft()
            if not node:
                seen_null = True
            else:
                if seen_null:
                    return False
                queue.append(node.left)
                queue.append(node.right)

        return True
Explanation:

  1. BFS enqueues both children (including None) for every node.
  2. Once a None is dequeued, every subsequent node must also be None.
  3. Any non-null after a null means a gap — tree is incomplete.

Time: O(n)  |  Space: O(w)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        def count_nodes(node):
            if not node:
                return 0
            return 1 + count_nodes(node.left) + count_nodes(node.right)

        def height(node):
            if not node:
                return 0
            return 1 + height(node.left)

        if not root:
            return True
        nodes = count_nodes(root)
        h = height(root)
        return (1 << (h - 1)) <= nodes <= (1 << h) - 1
Explanation:

  1. A complete tree with height h has between 2^(h-1) and 2^h - 1 nodes.
  2. Count nodes and height; verify the count fits the complete-tree range.
  3. Alternative mathematical check — BFS sentinel is more direct in interviews.

Time: O(n)  |  Space: O(h)

Problem 5: Cousins in Binary Tree (Leetcode:993)#

Problem Statement

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Constraints:

  • The number of nodes in the tree is in the range [2, 100].
  • 1 <= Node.val <= 100
  • Each node has a unique value.
  • x != y
  • x and y are exist in the tree.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        queue = deque([(root, None)])
        while queue:
            level_size = len(queue)
            parents = {}
            for _ in range(level_size):
                node, parent = queue.popleft()
                if node.left:
                    parents[node.left.val] = node.val
                    queue.append((node.left, node))
                if node.right:
                    parents[node.right.val] = node.val
                    queue.append((node.right, node))
            if x in parents and y in parents:
                return parents[x] != parents[y]
        return False
Explanation:

  1. BFS level by level; record each child's parent value at the current depth.
  2. If both x and y appear at the same level, they are cousins iff they have different parents.
  3. Same parent at the same depth means siblings, not cousins.

Time: O(n)  |  Space: O(w)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        info = {}

        def dfs(node, parent, depth):
            if not node:
                return
            if node.val in (x, y):
                info[node.val] = (depth, parent.val if parent else -1)
            dfs(node.left, node, depth + 1)
            dfs(node.right, node, depth + 1)

        dfs(root, None, 0)
        return info[x][0] == info[y][0] and info[x][1] != info[y][1]
Explanation:

  1. DFS stores (depth, parent_val) for x and y.
  2. Cousins share depth but have different parents.
  3. Compact when the tree is deep and targets are few.

Time: O(n)  |  Space: O(h)

Problem 6: Maximum Difference Between Node and Ancestor (Leetcode:1026)#

Problem Statement

Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

Example 1:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation:
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Example 2:

Input: root = [1,null,2,null,0,3]
Output: 3

Constraints:

  • The number of nodes in the tree is in the range [2, 5000].
  • 0 5
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        self.result = 0

        def dfs(node, min_val, max_val):
            if not node:
                return
            min_val = min(min_val, node.val)
            max_val = max(max_val, node.val)
            self.result = max(self.result, node.val - min_val, max_val - node.val)
            dfs(node.left, min_val, max_val)
            dfs(node.right, min_val, max_val)

        dfs(root, root.val, root.val)
        return self.result
Explanation:

  1. At each node, the max ancestor difference uses the min and max values on the root-to-node path.
  2. Update result with node.val - min_val and max_val - node.val.
  3. Pass updated min/max to children.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return float("inf"), float("-inf"), 0
            if not node.left and not node.right:
                return node.val, node.val, 0
            left_min, left_max, left_diff = dfs(node.left)
            right_min, right_max, right_diff = dfs(node.right)
            subtree_min = min(node.val, left_min, right_min)
            subtree_max = max(node.val, left_max, right_max)
            best = max(
                left_diff,
                right_diff,
                node.val - min(left_min, right_min),
                max(left_max, right_max) - node.val,
            )
            return subtree_min, subtree_max, best

        return dfs(root)[2]
Explanation:

  1. Postorder returns (subtree_min, subtree_max, best_diff) for each subtree.
  2. At each node, compare against min/max from left and right children.
  3. Aggregates the global maximum bottom-up.

Time: O(n)  |  Space: O(h)

Problem 7: Number of Good Leaf Nodes Pairs (Leetcode:1530)#

Problem Statement

You are given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation:
The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation:
The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation:
The only good pair is [2,5].

Constraints:

  • The number of nodes in the tree is in the range [1, 210].
  • 1 <= Node.val <= 100
  • 1 <= distance <= 10
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def countPairs(self, root: Optional[TreeNode], distance: int) -> int:
        self.count = 0

        def dfs(node):
            if not node:
                return []
            if not node.left and not node.right:
                return [0]
            distances = []
            for d in dfs(node.left) + dfs(node.right):
                if d + 2 <= distance:
                    distances.append(d + 1)
            for i in range(len(distances)):
                for j in range(i + 1, len(distances)):
                    if distances[i] + distances[j] + 2 <= distance:
                        self.count += 1
            return distances

        dfs(root)
        return self.count
Explanation:

  1. Each DFS call returns distances from the current node to leaves in its subtree.
  2. Pair leaves from left and right subtrees whose combined path length ≤ distance.
  3. Increment count for every valid cross-subtree leaf pair at each internal node.

Time: O(n · L²) where L = leaves per subtree  |  Space: O(h)

 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
class Solution:
    def countPairs(self, root: Optional[TreeNode], distance: int) -> int:
        self.count = 0

        def dfs(node):
            if not node:
                return [0] * (distance + 1)
            if not node.left and not node.right:
                freq = [0] * (distance + 1)
                freq[0] = 1
                return freq

            left_freq = dfs(node.left)
            right_freq = dfs(node.right)
            for d1 in range(distance):
                if not left_freq[d1]:
                    continue
                for d2 in range(distance - d1 - 2):
                    if right_freq[d2]:
                        self.count += left_freq[d1] * right_freq[d2]

            merged = [0] * (distance + 1)
            for d in range(distance):
                merged[d + 1] = left_freq[d] + right_freq[d]
            return merged

        dfs(root)
        return self.count
Explanation:

  1. Return a frequency array of leaf distances instead of a raw list.
  2. Cross-multiply left/right frequencies to count valid pairs in O(distance²) per node.
  3. More efficient when distance is small (≤ 10 per constraints).

Time: O(n · d²)  |  Space: O(n · d)

Problem 8: Smallest Subtree with all the Deepest Nodes (Leetcode:865)#

Problem Statement

Given the root of a binary tree, the depth of each node is the shortest distance to the root.

Return the smallest subtree such that it contains all the deepest nodes in the original tree.

A node is called the deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation:
We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

Example 2:

Input: root = [1]
Output: [1]
Explanation:
The root is the deepest node in the tree.

Example 3:

Input: root = [0,1,3,null,2]
Output: [2]
Explanation:
The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.

Constraints:

  • The number of nodes in the tree will be in the range [1, 500].
  • 0 <= Node.val <= 500
  • The values of the nodes in the tree are unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node):
            if not node:
                return 0, None
            left_depth, left_node = dfs(node.left)
            right_depth, right_node = dfs(node.right)
            if left_depth > right_depth:
                return left_depth + 1, left_node
            if right_depth > left_depth:
                return right_depth + 1, right_node
            return left_depth + 1, node

        return dfs(root)[1]
Explanation:

  1. Identical core logic to LCA of Deepest Leaves (LeetCode 1123).
  2. Return the node where left and right deepest depths meet.
  3. Single O(n) postorder pass.

Time: O(n)  |  Space: O(h)

 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
class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        parent, deepest, max_depth = {root: None}, [], 0
        stack = [(root, 0)]
        while stack:
            node, depth = stack.pop()
            if depth > max_depth:
                max_depth, deepest = depth, [node]
            elif depth == max_depth:
                deepest.append(node)
            if node.left:
                parent[node.left] = node
                stack.append((node.left, depth + 1))
            if node.right:
                parent[node.right] = node
                stack.append((node.right, depth + 1))

        def lca(a, b):
            seen = set()
            while a:
                seen.add(a)
                a = parent[a]
            while b not in seen:
                b = parent[b]
            return b

        ans = deepest[0]
        for node in deepest[1:]:
            ans = lca(ans, node)
        return ans
Explanation:

  1. Pass 1: DFS collects all deepest nodes and builds a parent map.
  2. Pass 2: Pairwise LCA of deepest nodes yields the smallest containing subtree.
  3. Clearer to reason about but uses extra space.

Time: O(n)  |  Space: O(n)

Problem 9: All Nodes Distance K in Binary Tree (Leetcode:863)#

Problem Statement

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation:
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

Example 2:

Input: root = [1], target = 1, k = 3
Output: []

Constraints:

  • The number of nodes in the tree is in the range [1, 500].
  • 0 <= Node.val <= 500
  • All the values Node.val are unique.
  • target is the value of one of the nodes in the tree.
  • 0 <= k <= 1000
Code and Explanation 

 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
class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        parent = {root: None}
        stack = [root]
        while stack:
            node = stack.pop()
            if node.left:
                parent[node.left] = node
                stack.append(node.left)
            if node.right:
                parent[node.right] = node
                stack.append(node.right)

        queue = deque([(target, 0)])
        visited = {target}
        result = []

        while queue:
            node, dist = queue.popleft()
            if dist == k:
                result.append(node.val)
            elif dist < k:
                for nxt in (node.left, node.right, parent[node]):
                    if nxt and nxt not in visited:
                        visited.add(nxt)
                        queue.append((nxt, dist + 1))

        return result
Explanation:

  1. Trees lack parent pointers — build a parent map first.
  2. BFS from target treating edges as undirected (left, right, parent).
  3. Collect values when distance equals k.

Time: O(n)  |  Space: O(n)

 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
class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        graph = defaultdict(list)

        def build(node, par):
            if not node:
                return
            if par:
                graph[node].append(par)
                graph[par].append(node)
            build(node.left, node)
            build(node.right, node)

        build(root, None)
        result = []
        visited = {target}

        def dfs(node, dist):
            if dist == k:
                result.append(node.val)
                return
            for nxt in graph[node]:
                if nxt not in visited:
                    visited.add(nxt)
                    dfs(nxt, dist + 1)

        dfs(target, 0)
        return result
Explanation:

  1. Build an undirected adjacency list from the tree.
  2. DFS from target outward to distance k.
  3. Equivalent to BFS; choose based on comfort with graphs.

Time: O(n)  |  Space: O(n)

Problem 10: Find a Corresponding Node of a Binary Tree in a Clone of That Tree (Leetcode:1379)#

Problem Statement

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation:
In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target = 7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • The values of the nodes of the tree are unique.
  • target node is a node from the original tree and is not null.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        def dfs(o, c):
            if not o:
                return None
            if o is target:
                return c
            left = dfs(o.left, c.left)
            return left if left else dfs(o.right, c.right)

        return dfs(original, cloned)
Explanation:

  1. Traverse both trees in lockstep — same structure guarantees matching positions.
  2. Return the cloned node when the original pointer equals target.
  3. O(n) worst case, often faster if target is shallow.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        queue = deque([(original, cloned)])
        while queue:
            o, c = queue.popleft()
            if o is target:
                return c
            if o.left:
                queue.append((o.left, c.left))
            if o.right:
                queue.append((o.right, c.right))
Explanation:

  1. BFS enqueues (original, cloned) pairs level by level.
  2. First match on the original side returns the paired cloned node.
  3. Same logic as DFS; useful when recursion depth is a concern.

Time: O(n)  |  Space: O(w)

Problem 11: All Possible Full Binary Trees (Leetcode:894)#

Problem Statement

Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Example 1:

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

Example 2:

Input: n = 3
Output: [[0,0,0]]

Constraints:

  • 1 <= n <= 20
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        memo = {0: [], 1: [TreeNode()]}

        def build(count):
            if count in memo:
                return memo[count]
            trees = []
            for left_count in range(1, count - 1, 2):
                right_count = count - 1 - left_count
                for left in build(left_count):
                    for right in build(right_count):
                        root = TreeNode(0, left, right)
                        trees.append(root)
            memo[count] = trees
            return trees

        return build(n) if n % 2 == 1 else []
Explanation:

  1. A full binary tree with n nodes exists only when n is odd.
  2. Split n-1 remaining nodes into odd left_count and right_count; combine all pairs.
  3. Memoize subproblem results to avoid rebuilding identical subtrees.

Time: O(2^n) output size  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n % 2 == 0:
            return []
        dp = [[] for _ in range(n + 1)]
        dp[1] = [TreeNode()]

        for count in range(3, n + 1, 2):
            for left_count in range(1, count - 1, 2):
                right_count = count - 1 - left_count
                for left in dp[left_count]:
                    for right in dp[right_count]:
                        dp[count].append(TreeNode(0, left, right))

        return dp[n]
Explanation:

  1. Fill dp[count] for odd counts from 3 to n.
  2. Same split-and-combine logic as recursion, but iterative tabulation.
  3. Avoids recursion depth and repeated memo lookups.

Time: O(2^n)  |  Space: O(n)

Problem 12: Delete Leaves With a Given Value (Leetcode:1325)#

Problem Statement

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you cannot).

Example 1:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation:
Leaf nodes in green with value (target = 2) are removed (Picture in left).
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

Example 2:

Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]

Example 3:

Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation:
Leaf nodes in green with value (target = 2) are removed at each step.

Constraints:

  • The number of nodes in the tree is in the range [1, 3000].
  • 1 <= Node.val, target <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        def dfs(node):
            if not node:
                return None
            node.left = dfs(node.left)
            node.right = dfs(node.right)
            if not node.left and not node.right and node.val == target:
                return None
            return node

        return dfs(root)
Explanation:

  1. Postorder: process children before the parent so leaves are identified correctly.
  2. After pruning children, if the current node is a matching leaf, return None.
  3. Repeated passes happen naturally as parents become new leaves.

Time: O(n)  |  Space: O(h)

 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
class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        if not root:
            return None
        stack, last = [(root, False)], None

        def is_leaf(node):
            return node and not node.left and not node.right

        while stack:
            node, visited = stack[-1]
            if visited:
                stack.pop()
                if is_leaf(node) and node.val == target:
                    if not stack:
                        return None
                    parent, _ = stack[-1]
                    if parent.left is node:
                        parent.left = None
                    else:
                        parent.right = None
                last = node
            elif node.right and node.right is not last:
                stack.append((node.right, False))
            elif node.left:
                stack.append((node.left, False))
            else:
                stack[-1] = (node, True)

        return root
Explanation:

  1. Explicit postorder stack processes leaves before their parents.
  2. Detach matching leaves from the parent pointer.
  3. Mirrors the recursive solution without call-stack depth limits.

Time: O(n)  |  Space: O(h)

Problem 13: Delete Nodes And Return Forest (Leetcode:1110)#

Problem Statement

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Example 2:

Input: root = [1,2,4,null,3], to_delete = [3]
Output: [[1,2,4]]

Constraints:

  • The number of nodes in the given tree is at most 1000.
  • Each node has a distinct value between 1 and 1000.
  • to_delete.length <= 1000
  • to_delete contains distinct values between 1 and 1000.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        to_delete_set = set(to_delete)
        forest = []

        def dfs(node, is_root):
            if not node:
                return None
            deleted = node.val in to_delete_set
            if is_root and not deleted:
                forest.append(node)
            node.left = dfs(node.left, deleted)
            node.right = dfs(node.right, deleted)
            return None if deleted else node

        dfs(root, True)
        return forest
Explanation:

  1. A node becomes a new forest root if it is not deleted and its parent was deleted (or it is the original root).
  2. Postorder removes deleted nodes by returning None to the parent.
  3. Children of deleted nodes are re-entered DFS with is_root=True.

Time: O(n)  |  Space: O(h + |to_delete|)

 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
class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        to_delete_set = set(to_delete)
        forest = []
        parent = {root: None}
        queue = deque([root])

        while queue:
            node = queue.popleft()
            if node.left:
                parent[node.left] = node
                queue.append(node.left)
            if node.right:
                parent[node.right] = node
                queue.append(node.right)

        for node in list(parent.keys()):
            if node.val not in to_delete_set:
                par = parent[node]
                if par is None or par.val in to_delete_set:
                    forest.append(node)
            else:
                par = parent[node]
                if par:
                    if par.left is node:
                        par.left = None
                    else:
                        par.right = None

        return forest
Explanation:

  1. BFS builds parent pointers, then scan all nodes.
  2. Non-deleted nodes whose parent is deleted (or absent) join the forest.
  3. Detach deleted nodes from their parents explicitly.

Time: O(n)  |  Space: O(n)

Problem 14: Find Duplicate Subtrees (Leetcode:652)#

Problem Statement

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

Constraints:

  • The number of the nodes in the tree will be in the range [1, 5000]
  • -200 <= Node.val <= 200
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        count = defaultdict(int)
        result = []

        def serialize(node):
            if not node:
                return "#"
            key = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
            count[key] += 1
            if count[key] == 2:
                result.append(node)
            return key

        serialize(root)
        return result
Explanation:

  1. Serialize each subtree as val,left,right string keys.
  2. Increment a counter; on the second occurrence, add the subtree root to results.
  3. Postorder ensures children are serialized before the parent.

Time: O(n²) string building  |  Space: O(n²)

 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
class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        triplet_to_id = {}
        count = defaultdict(int)
        result = []
        uid = 0

        def encode(node):
            nonlocal uid
            if not node:
                return 0
            left_id = encode(node.left)
            right_id = encode(node.right)
            triplet = (node.val, left_id, right_id)
            if triplet not in triplet_to_id:
                uid += 1
                triplet_to_id[triplet] = uid
            tid = triplet_to_id[triplet]
            count[tid] += 1
            if count[tid] == 2:
                result.append(node)
            return tid

        encode(root)
        return result
Explanation:

  1. Assign each unique subtree shape an integer ID via (val, left_id, right_id) triplets.
  2. Avoids long string concatenation — more efficient for large trees.
  3. Still postorder; duplicate detection on second ID occurrence.

Time: O(n)  |  Space: O(n)

Problem 15: House Robber III (Leetcode:337)#

Problem Statement

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police**.

Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation:
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation:
Maximum amount of money the thief can rob = 4 + 5 = 9.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • 0 4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0, 0
            left_rob, left_skip = dfs(node.left)
            right_rob, right_skip = dfs(node.right)
            rob = node.val + left_skip + right_skip
            skip = max(left_rob, left_skip) + max(right_rob, right_skip)
            return rob, skip

        return max(dfs(root))
Explanation:

  1. Return (rob_current, skip_current) for each subtree.
  2. Rob = node value + best skip values from children (cannot rob adjacent nodes).
  3. Skip = sum of max(rob, skip) from each child. Answer is max at the root.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        memo = {}

        def dfs(node):
            if not node:
                return 0
            if node in memo:
                return memo[node]
            rob = node.val
            if node.left:
                rob += dfs(node.left.left) + dfs(node.left.right)
            if node.right:
                rob += dfs(node.right.left) + dfs(node.right.right)
            skip = dfs(node.left) + dfs(node.right)
            memo[node] = max(rob, skip)
            return memo[node]

        return dfs(root)
Explanation:

  1. Alternative recurrence: robbing a node skips its children but includes grandchildren.
  2. Memoize per-node results to avoid recomputation in the naive recursion.
  3. Same optimal answer; tuple approach is cleaner for trees.

Time: O(n)  |  Space: O(n)

Problem 16: Step-By-Step Directions From a Binary Tree Node to Another (Leetcode:2096)#

Problem Statement

You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.

Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:

Return the step-by-step directions of the shortest path from node s to node t.

Example 1:

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation:
The shortest path is: 3 → 1 → 5 → 2 → 6.

Example 2:

Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation:
The shortest path is: 2 → 1.

Constraints:

  • The number of nodes in the tree is n.
  • 2 5
  • 1 <= Node.val <= n
  • All the values in the tree are unique.
  • 1 <= startValue, destValue <= n
  • startValue != destValue
Code and Explanation 

 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
class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        def find_path(node, target, path):
            if not node:
                return False
            if node.val == target:
                return True
            path.append("L")
            if find_path(node.left, target, path):
                return True
            path[-1] = "R"
            if find_path(node.right, target, path):
                return True
            path.pop()
            return False

        path_start, path_dest = [], []
        find_path(root, startValue, path_start)
        find_path(root, destValue, path_dest)

        i = 0
        while i < len(path_start) and i < len(path_dest) and path_start[i] == path_dest[i]:
            i += 1

        ups = "U" * (len(path_start) - i)
        return ups + "".join(path_dest[i:])
Explanation:

  1. Build root-to-node paths for start and dest as L/R strings.
  2. Strip the common prefix — that shared path ends at the LCA.
  3. Go up from start (U repeated) then follow the remaining dest path.

Time: O(n)  |  Space: O(n)

 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
class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        parent = {root: None}

        def build(node):
            if node.left:
                parent[node.left] = node
                build(node.left)
            if node.right:
                parent[node.right] = node
                build(node.right)

        build(root)

        start, dest = None, None
        stack = [root]
        while stack:
            node = stack.pop()
            if node.val == startValue:
                start = node
            if node.val == destValue:
                dest = node
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)

        path_start = []
        while start != dest:
            path_start.append(start)
            start = parent[start]

        ups = "U" * len(path_start)
        down = []
        node = dest
        while node not in path_start:
            down.append("L" if parent[node].left is node else "R")
            node = parent[node]
        return ups + "".join(reversed(down))
Explanation:

  1. Build parent map, climb from start toward dest recording U steps.
  2. Trace L/R from LCA down to dest.
  3. Equivalent path logic using explicit parent pointers.

Time: O(n)  |  Space: O(n)

Problem 17: Populating Next Right Pointers in Each Node II (Leetcode:117)#

Problem Statement

Given a binary tree

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation:
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 6000].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def connect(self, root: Optional[Node]) -> Optional[Node]:
        if not root:
            return None
        queue = deque([root])

        while queue:
            level_size = len(queue)
            for i in range(level_size):
                node = queue.popleft()
                if i < level_size - 1:
                    node.next = queue[0]
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return root
Explanation:

  1. BFS processes each level; link each node to the next queue front.
  2. Last node at each level has next = None implicitly.
  3. O(n) time; uses O(w) extra space for the queue.

Time: O(n)  |  Space: O(w)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def connect(self, root: Optional[Node]) -> Optional[Node]:
        curr = root
        while curr:
            dummy = Node(0)
            tail = dummy
            while curr:
                if curr.left:
                    tail.next = curr.left
                    tail = tail.next
                if curr.right:
                    tail.next = curr.right
                    tail = tail.next
                curr = curr.next
            curr = dummy.next
        return root
Explanation:

  1. Use the already-linked next pointers to traverse the current level.
  2. Build the next level's linked list with a dummy head (tail pointer).
  3. O(1) extra space — optimal for follow-up constraints.

Time: O(n)  |  Space: O(1)

Problem 18: Distribute Coins in Binary Tree (Leetcode:979)#

Problem Statement

You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.

In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.

Return the minimum number of moves required to make every node have exactly one coin.

Example 1:

Input: root = [3,0,0]
Output: 2
Explanation:
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: root = [0,3,0]
Output: 3
Explanation:
Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= n <= 100
  • 0 <= Node.val <= n
  • The sum of all Node.val is n.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        self.moves = 0

        def dfs(node):
            if not node:
                return 0
            left_excess = dfs(node.left)
            right_excess = dfs(node.right)
            self.moves += abs(left_excess) + abs(right_excess)
            return node.coins - 1 + left_excess + right_excess

        dfs(root)
        return self.moves
Explanation:

  1. Each subtree returns excess coins (positive = surplus, negative = deficit).
  2. Moving |excess| coins across an edge costs that many moves.
  3. Sum absolute excess flows from children at every node.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        stack, excess, moves, last = [(root, False)], {}, 0, None

        while stack:
            node, visited = stack[-1]
            if visited or (not node.left and not node.right):
                stack.pop()
                left = excess.get(node.left, 0)
                right = excess.get(node.right, 0)
                moves += abs(left) + abs(right)
                excess[node] = node.coins - 1 + left + right
                last = node
            elif node.right and node.right is not last:
                stack.append((node.right, False))
            elif node.left:
                stack.append((node.left, False))
            else:
                stack[-1] = (node, True)

        return moves
Explanation:

  1. Same excess-flow logic with an explicit postorder stack.
  2. Store subtree excess in a hash map; accumulate moves on node completion.
  3. Avoids recursion on very deep trees.

Time: O(n)  |  Space: O(n)

Problem 19: Serialize and Deserialize Binary Tree (Leetcode:297)#

Problem Statement

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000
Code and Explanation 

 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
class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        if not root:
            return ""
        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")
        return ",".join(result)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data:
            return None
        values = deque(data.split(","))
        root = TreeNode(int(values.popleft()))
        queue = deque([root])
        while queue:
            node = queue.popleft()
            left_val = values.popleft()
            if left_val != "null":
                node.left = TreeNode(int(left_val))
                queue.append(node.left)
            right_val = values.popleft()
            if right_val != "null":
                node.right = TreeNode(int(right_val))
                queue.append(node.right)
        return root
Explanation:

  1. BFS encodes nodes level by level, using "null" for missing children.
  2. Deserialize reads values in the same order, attaching left then right children.
  3. Compact and matches LeetCode's array representation.

Time: O(n) serialize & deserialize  |  Space: O(n)

 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
class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        tokens = []

        def dfs(node):
            if not node:
                tokens.append("null")
                return
            tokens.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(tokens)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        values = iter(data.split(","))

        def dfs():
            val = next(values)
            if val == "null":
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()
Explanation:

  1. Preorder DFS with "null" markers uniquely defines tree structure.
  2. Deserialize consumes tokens in the same preorder sequence.
  3. Often shorter strings than BFS for sparse trees.

Time: O(n)  |  Space: O(n)

Problem 20: Binary Tree Cameras (Leetcode:968)#

Problem Statement

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: root = [0,0,null,0,0]
Output: 1
Explanation:
One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation:
At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • Node.val == 0
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        self.cameras = 0

        def dfs(node):
            if not node:
                return 2
            left = dfs(node.left)
            right = dfs(node.right)
            if left == 0 or right == 0:
                self.cameras += 1
                return 1
            if left == 1 or right == 1:
                return 2
            return 0

        return self.cameras + (1 if dfs(root) == 0 else 0)
Explanation:

  1. States: 0 = uncovered, 1 = has camera, 2 = covered (no camera).
  2. If any child is uncovered (0), place a camera at the current node.
  3. If any child has a camera (1), current node is covered. Add a root camera if the root remains uncovered.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0, 0, float("inf")
            left = dfs(node.left)
            right = dfs(node.right)
            placed = 1 + left[1] + right[1]
            not_placed_covered = min(left[2], left[0]) + min(right[2], right[0])
            not_placed_uncovered = left[1] + right[1]
            return (
                min(placed, not_placed_covered),
                not_placed_uncovered,
                min(placed, not_placed_covered),
            )

        placed, _, covered = dfs(root)
        return min(placed, covered)
Explanation:

  1. Each node tracks three costs: camera here, covered without camera, uncovered.
  2. Combine child states to minimize cameras bottom-up.
  3. More verbose than the greedy state machine but illustrates tree DP thinking.

Time: O(n)  |  Space: O(h)