DSA sheet · Trees · Binary search tree pattern

Merge Two Binary Trees

The sheet calls this "merge two BSTs", but the video really covers two different questions with that name. On LeetCode, you lay one tree on top of another and add up the nodes that overlap. The trees there are normal binary trees, not BSTs. On GFG, you get two real BSTs and must return all their values as one sorted array. The teacher solves both. The first one teaches a key habit of the construction pattern: when a recursive call returns a node, you must store it somewhere. The second one reuses two things we already know: inorder of a BST is sorted, and how to merge two sorted arrays.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Merge Two Binary Trees (LeetCode) with DFS
• Part B · Merge Two BSTs into a sorted array (GFG)
• Part C · Revision page

Part 0 · Before starting

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

Binary tree vs binary search tree (BST)

• A binary tree: every node has at most 2 children. There is no rule about the values.
• A binary search tree (BST): a binary tree with an order rule. Everything in a node's left subtree is smaller than the node, and everything in its right subtree is bigger.

Inorder traversal

Inorder = left subtree, then the node, then the right subtree. On a BST this visits the values in sorted order, because everything smaller sits on the left. We need this fact in Part B.

Overlap

Picture putting tree 2 on top of tree 1, root on root. Two nodes overlap when both trees have a node at the same position (same path of lefts and rights from the root).

Part A · Merge Two Binary Trees (LeetCode) with DFS

LeetCode 617

1The question in simple words

You get two binary trees, root1 and root2. Lay one over the other and build the merged tree:

• If both trees have a node at a position → the merged node's value is the sum of the two.
• If only one tree has a node there → that node is used as it is.
• If neither has a node → nothing there.

Return the root of the merged tree.

      1
     / \
    3   2
   /
  5

      2
     / \
    1   3
     \   \
      4   7

      3
     / \
    4   5
   / \   \
  5   4   7

Root: 1 + 2 = 3. Left: 3 + 1 = 4. Left of that: 5 in tree 1, nothing in tree 2 → stays 5. Right of 4: nothing in tree 1, 4 in tree 2 → 4. Right of the root: 2 + 3 = 5, and its right child is only in tree 2 → 7.

2What the constraints tell us

• Nodes in each tree: 0 to 2000 → a tree can be empty. We need base cases for None.
• Values: −10⁴ to 10⁴. The teacher asks: how many values do we ever add together? Only two at a time (one from each tree). The biggest sum is 2 × 10⁴, far below the int limit of about 10⁹. So no long is needed. (Python ints never overflow anyway.)
• n ≤ 2000 is small, so a simple O(n) recursion is more than enough.

3Intuition: two fingers again, and write the answer into tree 1

Like in Same Tree, put one finger on each tree and move them together: left with left, right with right. At each position, the finger tells you whether a node exists there.

Where do we keep the answer? We could build a brand-new tree, but that means creating up to n new nodes. The teacher's choice: use tree 1 as the result. Wherever both nodes exist, overwrite tree 1's value with the sum. Wherever tree 1 has nothing but tree 2 has a node, just borrow tree 2's node. (Using tree 2 as the result works the same way, with the roles swapped.)

4Building the conditions from examples

She first asks when the addition can happen at all:

• Both None → nothing to add.
• One exists, the other is None → nothing to add. The existing one is simply kept.
• Only when both exist do we add.

Base case 1: root1 is None → return root2

If tree 1 has nothing here, merging "nothing" with tree 2's part gives tree 2's part. Return root2.

Base case 2: root2 is None → return root1

We only get here if root1 exists. Tree 2 has nothing to add, so tree 1's part stays as it is. Return root1.

Both exist → add, then go left and right

root1.val += root2.val. Then the children. With root1's left child, which node of tree 2 overlaps? Its left child, of course. So the calls are (root1.left, root2.left) and (root1.right, root2.right).

The key habit: save what the call returns

The function returns a node (the root of the merged subtree). That node must be hung back in the right place. Whatever the left call returns must become root1.left, and the right call's result becomes root1.right.

Finally return root1

After both sides are done, this node is complete. Return root1 so that the parent can store it in its own left or right.

5Approach steps

1. If root1 is None → return root2.
2. If root2 is None → return root1.
3. Both exist: root1.val += root2.val.
4. root1.left = merge(root1.left, root2.left).
5. root1.right = merge(root1.right, root2.right).
6. Return root1.

6Code (Python)

class Solution:
    def mergeTrees(self, root1, root2):
        if root1 is None:            # nothing in tree 1 (also covers both None)
            return root2
        if root2 is None:            # nothing to add from tree 2
            return root1
        root1.val += root2.val       # both exist: add into tree 1
        root1.left = self.mergeTrees(root1.left, root2.left)      # save the result!
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

7Code line by line

8Dry run using the call stack

The trees from step 1. f(a, b) means mergeTrees(a, b). N = None.

1. f(1, 2): both exist → 1 becomes 3. Go left. (f(1,2) waits.)
2. f(3, 1): both exist → 3 becomes 4. Go left.
3. f(5, N): root1 = 5 exists, root2 is None → return 5. It's stored as 4's left (no change).
4. Back in f(3,1), go right: f(N, 4): root1 is None → return tree 2's node 4. Stored as root1.right, so 4 now has right child 4.
5. f(3,1) is done → returns its node (value 4) to f(1,2), which stores it as its left.
6. f(1,2) goes right: f(2, 3): both exist → 2 becomes 5. Go left.
7. f(N, N): root1 is None → return root2, which is None. 5's left stays None.
8. Go right: f(N, 7): root1 is None → return node 7. Stored as 5's right.
9. f(2,3) returns its node (value 5) to f(1,2), stored as its right.
10. f(1,2) returns its node (value 3). The stack is empty. Final tree: 3 (4 (5, 4), 5 (–, 7)) ✓

9Complexity & remember

• Time O(n): each call handles one pair of overlapping positions and does constant work. (More precisely, we stop as soon as one side is None, so we only walk the positions where both trees have nodes. In the worst case that's every node.)
• Space O(height): the recursion goes deep down one side, then returns before going right. So the stack holds one call per level: about log n for a balanced tree, but n for a skewed tree (all left or all right children).

Part B · Merge Two BSTs into a sorted array (GFG)

GFG "Merge two BSTs"

1The question in simple words

The GFG problem with the same name is a different task. You get two BSTs. Return one sorted list with every value from both trees, duplicates included. You don't build any tree.

    3
   / \
  1   5

    4
   / \
  2   5

Answer: [1, 2, 3, 4, 5, 5]. Note that 5 appears twice, because it is in both trees.

2What the constraints tell us

• The teacher points out the total size can be about 2 × 10⁵. An O(n²) idea would be about 4 × 10¹⁰ steps, far above the ~10⁸ limit → TLE. We need something linear (O(n), maybe O(n log n)).
• Duplicates must be kept, so we can't use a set.

3Intuition: two sorted arrays for free

• An inorder traversal of a BST gives its values sorted. So BST 1 → [1, 3, 5] and BST 2 → [2, 4, 5].
• Now the problem is just merge two sorted arrays, which we already did in the arrays and linked-list topics. Use one pointer on each array, and always take the smaller front value.

4Building the merge logic

• Pointer i on array 1, j on array 2, both start at 0.
• Compare a[i] and b[j]. Put the smaller one in the result and move only that pointer.
• When one array runs out, everything left in the other array is already sorted and bigger, so copy it to the end as it is.

5Approach steps

1. Inorder of BST 1 → array a. Inorder of BST 2 → array b.
2. i = j = 0, empty res.
3. While both pointers are in range: append the smaller of a[i], b[j] and move that pointer.
4. Copy whatever is left in a, then whatever is left in b.
5. Return res.

6Code (Python)

class Solution:
    def merge(self, root1, root2):
        a, b = [], []
        self.inorder(root1, a)
        self.inorder(root2, b)

        res = []
        i = j = 0
        while i < len(a) and j < len(b):
            if a[i] <= b[j]:
                res.append(a[i])
                i += 1
            else:
                res.append(b[j])
                j += 1
        while i < len(a):              # leftovers from array 1
            res.append(a[i])
            i += 1
        while j < len(b):              # leftovers from array 2
            res.append(b[j])
            j += 1
        return res

    def inorder(self, node, arr):
        if node is None:
            return
        self.inorder(node.left, arr)   # left
        arr.append(node.val)           # node
        self.inorder(node.right, arr)  # right

7Code line by line

8Dry run

a = [1, 3, 5], b = [2, 4, 5].

Final answer [1, 2, 3, 4, 5, 5] ✓

9Complexity & remember

• Time: two inorder traversals O(n) + O(m), then one merge pass O(n + m) → linear overall. It passes the 2 × 10⁵ limit easily.
• Space: array a O(n) + array b O(m) + result O(n + m) → O(n + m), plus the recursion stack O(height).

Part C · Revision page

class Solution:
    def mergeTrees(self, root1, root2):
        if root1 is None and root2 is None:
            return None
        v1 = root1.val if root1 else 0
        v2 = root2.val if root2 else 0
        node = TreeNode(v1 + v2)                 # a new node every time
        node.left = self.mergeTrees(root1.left if root1 else None,
                                    root2.left if root2 else None)
        node.right = self.mergeTrees(root1.right if root1 else None,
                                     root2.right if root2 else None)
        return node

This one creates a node for every position and walks every node of both trees. The teacher's version reuses tree 1 and stops early when one side is missing.

r1 = TreeNode(1, TreeNode(3, TreeNode(5)), TreeNode(2))
r2 = TreeNode(2, TreeNode(1, None, TreeNode(4)), TreeNode(3, None, TreeNode(7)))
m = Solution().mergeTrees(r1, r2)
print(m.val, m.left.val, m.right.val)        # 3 4 5

b1 = TreeNode(3, TreeNode(1), TreeNode(5))
b2 = TreeNode(4, TreeNode(2), TreeNode(5))
print(Solution().merge(b1, b2))              # [1, 2, 3, 4, 5, 5]

Based on this video: Merge Two Binary Trees / Merge Two BSTs