Flatten a Search Tree Into a Chain

EasyTrees

Problem

Rearrange the nodes of a binary search tree so that they form a single chain in increasing order: the smallest value becomes the root, every node has no left child, and each node's right child is the next larger value.

Reuse the existing nodes and return the new root.

Example 1

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

Example 2

Input:
root = [5, 1, 7]
Output:
[1, null, 5, null, 7]

Constraints

  • 0 ≤ number of nodes ≤ 10^4
  • 0 ≤ node.val ≤ 10^5
  • All values are distinct.

Hint

Show the first hint

In what order must the nodes appear in the chain?

Walkthrough

How to approach it

01Clarify before coding

  • Create new nodes or reuse? Reuse the existing ones.
  • Must every left pointer be cleared? Yes, the chain uses right pointers only.
  • Empty tree? Return empty.

02Brute force

Collect the values in order and build a brand-new chain of nodes.

Cost: O(n) time and O(n) extra nodes, which the problem rules out by asking to reuse nodes.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.