Skip to content

Merge, Two Sum, Largest BST

Three Problems, Three Patterns

This lesson covers three BST problems that each connect back to a technique you already know. The goal: recognize the underlying pattern so you're not memorizing solutions — you're deriving them.

Problem 1: Merge Two BSTs

Given two BSTs, produce a single balanced BST containing all values from both.

You can't just insert every node from one tree into the other — that could give you a skewed tree. And even if it didn't, it's \(O(n \log n)\) per tree.

The approach that works: flatten both BSTs into sorted arrays (inorder traversal), merge the two sorted arrays (exactly like the merge step of merge sort), then build a balanced BST from the merged sorted array.

Flatten both BSTs to sorted arrays, merge them, then build a balanced BST

Step-by-Step

Tree A: 

    3
   / \
  1   5

Tree B: 

    4
   / \
  2   6

Step 1: Flatten via inorder.

Tree A → [1, 3, 5] Tree B → [2, 4, 6]

Step 2: Merge two sorted arrays.

Pointer A Pointer B Pick Merged so far
1 2 1 [1]
3 2 2 [1, 2]
3 4 3 [1, 2, 3]
5 4 4 [1, 2, 3, 4]
5 6 5 [1, 2, 3, 4, 5]
— 6 6 [1, 2, 3, 4, 5, 6]

Step 3: Build balanced BST from sorted array. Pick the middle element as root, recurse on left half and right half.

Sorted: [1, 2, 3, 4, 5, 6]. Middle index = 2 → root = 3. Left half [1, 2] → middle = 1, right child 2. Right half [4, 5, 6] → middle = 5, left child 4, right child 6.

      3
     / \
    1   5
     \ / \
     2 4  6

Balanced. All values present. BST property holds.

The Code

void flattenToSorted(TreeNode* root, vector<int>& result) {
    if (!root) return;
    flattenToSorted(root->left, result);
    result.push_back(root->value);
    flattenToSorted(root->right, result);
}

vector<int> mergeSortedArrays(vector<int>& first, vector<int>& second) {
    vector<int> merged;
    int indexFirst = 0, indexSecond = 0;
    while (indexFirst < (int)first.size() && indexSecond < (int)second.size()) {
        if (first[indexFirst] <= second[indexSecond])
            merged.push_back(first[indexFirst++]);
        else
            merged.push_back(second[indexSecond++]);
    }
    while (indexFirst < (int)first.size()) merged.push_back(first[indexFirst++]);
    while (indexSecond < (int)second.size()) merged.push_back(second[indexSecond++]);
    return merged;
}

TreeNode* buildBalancedBST(vector<int>& sortedValues, int start, int end) {
    if (start > end) return nullptr;
    int mid = start + (end - start) / 2;
    TreeNode* node = new TreeNode(sortedValues[mid]);
    node->left = buildBalancedBST(sortedValues, start, mid - 1);
    node->right = buildBalancedBST(sortedValues, mid + 1, end);
    return node;
}

Complexity: \(O(n + m)\) time and space, where \(n\) and \(m\) are the sizes of the two trees.

Problem 2: Two Sum in BST (LC 653)

Problem: Given a BST and a target sum, determine if any two nodes have values that add up to the target.

The brute force: for every node, search the BST for target - node.value. That's \(O(n \log n)\) for a balanced tree.

The better approach: use the BST's sorted order. Flatten to a sorted array, then use two pointers — one from the start, one from the end — exactly like Two Sum on a sorted array.

But there's an even cleaner approach that skips the array entirely: use two BST iterators. One walks forward (smallest to largest), the other walks backward (largest to smallest). This is a controlled inorder traversal — the same iterative inorder from the previous lesson, but you advance each iterator one step at a time.

Trace: Target = 9

        5
       / \
      3   7
     / \ / \
    2  4 6  8
Left Pointer Right Pointer Sum Action
2 8 10 \(10 > 9\) → move right pointer back
2 7 9 Found

Two steps. Done.

The Code (Array + Two Pointers)

bool findTwoSumBST(TreeNode* root, int target) {
    vector<int> sortedValues;
    flattenToSorted(root, sortedValues);

    int leftIndex = 0;
    int rightIndex = (int)sortedValues.size() - 1;

    while (leftIndex < rightIndex) {
        int currentSum = sortedValues[leftIndex] + sortedValues[rightIndex];
        if (currentSum == target) return true;
        if (currentSum < target) leftIndex++;
        else rightIndex--;
    }
    return false;
}

Complexity: \(O(n)\) time, \(O(n)\) space.

The BST iterator approach achieves \(O(n)\) time with \(O(h)\) space — you maintain two stacks of height \(h\) instead of materializing the whole array. Worth implementing if space matters.

Problem 3: Largest BST in Binary Tree (LC 333)

Problem: Given a binary tree (not necessarily a BST), find the size of the largest subtree that IS a valid BST.

This is the most interesting problem here because it's NOT a BST-specific technique. It's a postorder pair-return problem from Chapter 3.

        10
       /  \
      5    15
     / \     \
    1   8    20

Is the entire tree a BST? No — 8 is in the left subtree of 10 but 8 < 10 is fine. And 15 is in the right subtree. Actually, wait — let's check. Inorder: 1, 5, 8, 10, 15, 20. That IS sorted. This whole tree IS a valid BST.

Try a trickier example:

        10
       /  \
      5    15
     / \   / \
    1   8 6  20

Node 6 is in the right subtree of 10, but 6 < 10. Invalid. The largest BST subtrees are 5(1, 8) with size 3, and 20 with size 1. Answer: 3.

Postorder pass propagates BST validity, min, max, and size upward from leaves

The Postorder Pattern

At each node, you need to know about your children before you can decide about yourself. That's postorder.

What information do you need from each subtree?

  1. Is it a valid BST?
  2. Its size (if it's a valid BST)
  3. The minimum value in the subtree
  4. The maximum value in the subtree

A node's subtree is a valid BST if: - Left subtree is a valid BST - Right subtree is a valid BST - Left subtree's max < current node's value - Right subtree's min > current node's value

If all four conditions hold, the current subtree is a valid BST with size = 1 + leftSize + rightSize. If not, pass up the larger of the two children's BST sizes.

Full Trace

        10
       /  \
      5    15
     / \   / \
    1   8 6  20
Node Left returns Right returns isBST? Size Min Max
1 (true, 0, inf, -inf) (true, 0, inf, -inf) Yes 1 1 1
8 (true, 0, inf, -inf) (true, 0, inf, -inf) Yes 1 8 8
5 (true, 1, 1, 1) (true, 1, 8, 8) \(1 < 5\) and \(8 > 5\)? Yes, but wait — \(8 > 5\) means left max < node. Check: leftMax=1 < 5, rightMin=8 > 5. Yes 3 1 8
6 (true, 0, inf, -inf) (true, 0, inf, -inf) Yes 1 6 6
20 (true, 0, inf, -inf) (true, 0, inf, -inf) Yes 1 20 20
15 (true, 1, 6, 6) (true, 1, 20, 20) leftMax=6 < 15? No! \(6 < 15\) is true. rightMin=20 > 15? Yes. Yes 3 6 20
10 (true, 3, 1, 8) (true, 3, 6, 20) leftMax=8 < 10? Yes. rightMin=6 > 10? No! Not BST — —

Node 10 fails because 6 (min of right subtree) is less than 10. The largest BST subtrees are size 3 (rooted at 5 and rooted at 15). Answer: 3.

The Code

struct BSTInfo {
    bool isBST;
    int size;
    int minValue;
    int maxValue;
};

BSTInfo findLargestBST(TreeNode* root, int& largestSize) {
    if (!root) return {true, 0, INT_MAX, INT_MIN};

    BSTInfo leftInfo = findLargestBST(root->left, largestSize);
    BSTInfo rightInfo = findLargestBST(root->right, largestSize);

    if (leftInfo.isBST && rightInfo.isBST &&
        leftInfo.maxValue < root->value &&
        rightInfo.minValue > root->value) {

        int currentSize = 1 + leftInfo.size + rightInfo.size;
        largestSize = max(largestSize, currentSize);

        int currentMin = leftInfo.size == 0 ? root->value : leftInfo.minValue;
        int currentMax = rightInfo.size == 0 ? root->value : rightInfo.maxValue;

        return {true, currentSize, currentMin, currentMax};
    }

    return {false, 0, 0, 0};
}

If you solved Chapter 3's pair-return problems, this should feel familiar. The struct BSTInfo is your multi-value return. The postorder structure is identical — process children first, combine at the current node.

Complexity: \(O(n)\) time, \(O(h)\) space.

Try It

The starter code has a findTwoSumBST function with a TODO. The tree has values 2, 3, 4, 5, 6, 7, 8 and the target is 9.

Predict before running: Which pairs sum to 9? 2+7, 3+6, 4+5. The function should return true.

Challenge: In the merge problem, what happens if the two BSTs have duplicate values? Does the algorithm still work? (Yes — the merge step handles equal elements correctly, and the resulting BST can have duplicates if you allow <= in the BST property.)

Challenge 2: Can you solve Two Sum in BST with \(O(h)\) space instead of \(O(n)\)? (Hint: use two stacks — one for forward inorder, one for reverse inorder.)

Edge Cases to Watch For

  • Two Sum with target that equals double the root: For example, tree has root 5 and target = 10. You need two DISTINCT nodes summing to 10, not the same node twice. The two-pointer approach handles this because leftIndex < rightIndex prevents using the same element. If you use a hash set approach instead, you must check that the two nodes are different.

Problems

Problem Link Difficulty
LC 653 — Two Sum IV (BST) leetcode.com/problems/two-sum-iv-input-is-a-bst Easy
LC 108 — Convert Sorted Array to BST leetcode.com/problems/convert-sorted-array-to-binary-search-tree Easy
LC 333 — Largest BST Subtree leetcode.com/problems/largest-bst-subtree Medium
LC 1305 — All Elements in Two BSTs leetcode.com/problems/all-elements-in-two-binary-search-trees Medium