Skip to content
Tutorials Center
My learning

Topics

Lesson 96 of 225 ยท Trees

BST Problems: Merge, Fix Swapped, Largest BST, List to BST

Four classic BST problems in Python: build a balanced BST from a sorted list, merge two BSTs, repair a BST with two swapped nodes, and find the largest BST in a tree.

You know what a binary search tree is and how to insert and look up keys. Interviews rarely stop there. They ask you to build, combine, repair and detect BSTs, and nearly every one of those problems comes down to one fact:

The inorder traversal of a valid BST is a strictly increasing sequence.

Four problems follow. For each we state the plain approach, then the improvement, then its cost. All examples share this small node class and a helper that builds a BST by inserting keys in order.

Python
class Node:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

Problem 1: Sorted list to balanced BST

Given a sorted list, build a height-balanced BST. Inserting the items one by one into a plain BST would produce a chain (O(n^2) total, height n). Instead pick the middle element as the root: everything left of it is smaller and goes into the left subtree, everything right is larger. Recurse on both halves. Each level halves the range, so the height is about log2(n) and the build is O(n).

Python Sorted list to balanced BST

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the data comes as a linked list instead of an array, you cannot jump to the middle in O(1). You can still do it in O(n) by building the left half first while advancing a single list pointer, so that the root is created exactly when the traversal reaches it (an inorder build). The simpler route is to copy the list into an array first, at the cost of O(n) extra space.

Problem 2: Merge two BSTs

Merge two BSTs into one valid BST containing all keys. Inserting every key of the smaller tree into the bigger one costs O(m log n), and is slow if the tree is unbalanced. A neater plan:

  1. Take the inorder lists of both trees (each sorted).
  2. Merge the two sorted lists with two pointers, as in merge sort.
  3. Build a balanced BST from the merged list (problem 1).

Time O(m + n), space O(m + n). The result is balanced regardless of the shapes of the inputs.

Python Merge two BSTs in linear time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Problem 3: Recover a BST with two swapped nodes

In a valid BST, exactly two nodes had their values swapped by mistake. Recover the tree without changing its structure. The inorder sequence should be increasing, but the swap creates "descents" (places where a value is smaller than the previous one):

  • Two adjacent swapped nodes (for example 1 3 2 4) create one descent.
  • Two non-adjacent swapped nodes (1 5 3 4 2 6) create two descents.

Walk the tree in inorder while remembering the previous node. At the first descent, record first = prev and second = node. If a second descent appears, update second = node. At the end swap the values of first and second. This needs only O(h) stack space and O(n) time, and no extra list.

Python Fix a BST with two swapped nodes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Problem 4: Largest BST inside a binary tree

You get an ordinary binary tree, not necessarily a BST. Find the size of the largest subtree that is a valid BST.

The straightforward approach checks every node: for each node, run a BST validity test (O(size)) and count nodes. That is O(n^2) on a skewed tree. The improvement is to compute the answer bottom-up in one pass: each call returns four facts about its subtree: is it a BST, its size, its minimum key and its maximum key. A node forms a BST if both children are BSTs, left.max < key, and right.min > key. Then the size is left.size + right.size + 1. Otherwise the node is not a BST and passes along the best size found below it.

Python Largest BST subtree in one pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Using inf and -inf for the empty tree lets the same comparison work without special cases.

Complexity summary

Problem Time Extra space
Sorted list to balanced BST O(n) O(log n) stack
Merge two BSTs (list route) O(m + n) O(m + n)
Recover swapped nodes O(n) O(h)
Largest BST in a tree O(n) O(h)

Common mistakes

  • Validating a BST by comparing each node only with its children. A node deep in the left subtree can still be larger than the root. Compare against the min and max of whole subtrees, or against running bounds.
  • Treating equal keys carelessly. Decide whether duplicates are allowed and where they go.
  • In the swap repair, updating first on the second descent. Only second changes.
  • Building a BST from sorted input with repeated insert, which gives a chain.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which traversal of a valid BST produces its keys in increasing order?

    Inorder visits the left subtree, then the node, then the right subtree, which matches the BST ordering rule at every node.
  2. 2. Why choose the middle element as the root when converting a sorted array to a BST?

    Splitting the range in half at every level keeps the height close to log2 n. Picking the first element would create a chain.
  3. 3. Two nodes of a BST are swapped, and the inorder sequence is 1 5 3 4 2 6. How many descents does it have, and which nodes need to be swapped back?

    The descents are 5 to 3 and 4 to 2. The first misplaced value is the larger one of the first descent (5); the second is the smaller one of the last descent (2).
  4. 4. What does each recursive call return in the one-pass largest-BST algorithm?

    A parent needs the size to count nodes and the min and max to check that its key fits between its subtrees, so all four facts travel up together.

Summary

  • The inorder traversal of a BST is sorted; most BST problems reduce to working with that sequence.
  • Sorted data becomes a balanced BST by recursively choosing the middle as the root.
  • Merging two BSTs: inorder lists, linear merge, then rebuild in O(m + n).
  • A BST with two swapped nodes shows one or two inorder descents; swap the first larger value with the last smaller value.
  • The largest BST in a general tree is found in one bottom-up pass returning (is_bst, size, min, max).

Next: Self-Balancing Trees: AVL