Convert a binary tree to a BST / balance a BST / flatten a BST to a sorted list

Medium

Problem

Three reshaping tasks. (1) Convert a binary tree into a BST while keeping its exact shape. (2) Turn a skewed BST into a height-balanced BST with the same values. (3) Flatten a BST into a sorted list that runs through right pointers, with every left pointer null.

Example 1

Input:  balance the skewed BST 1 → 2 → 3 → 4 (right children)
Output: [3, 2, 4, 1] or [2, 1, 3, null, null, null, 4]

Also asked as: Convert Binary tree into BST · Convert a normal BST into a Balanced BST · Flatten BST to sorted list

Test cases

Case 1

Input:    [10,2,7,8,4]
Expected: [8,4,10,2,7]

Case 2

Input:    [3,2,1]
Expected: [2,1,3]

Case 3

Input:    [2,1,3]
Expected: [2,1,3]

Case 4

Input:    [1]
Expected: [1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. In-order array ↔ balanced BST

Time O(n)Space O(n)

Collect the in-order values (sorted for a BST). To convert a plain binary tree: sort the collected values. To balance: recursively pick the middle as the root. To flatten: rebuild as a right-only chain.

function inorderVals(n, out = []) { if (n) { inorderVals(n.left, out); out.push(n.val); inorderVals(n.right, out); } return out; }
function sortedArrayToBST(a, lo = 0, hi = a.length - 1) {
if (lo > hi) return null;
const mid = (lo + hi) >> 1;
return { val: a[mid], left: sortedArrayToBST(a, lo, mid - 1), right: sortedArrayToBST(a, mid + 1, hi) };
}
function balanceBST(root) { return sortedArrayToBST(inorderVals(root)); }
function treeToBST(root) {
// keep the shape: write the sorted values back in in-order
const vals = inorderVals(root).sort((x, y) => x - y);
let i = 0;
const fill = (n) => { if (n) { fill(n.left); n.val = vals[i++]; fill(n.right); } };
fill(root);
return root;
}
function flattenToSortedList(root) {
const a = inorderVals(root);
const dummy = { right: null }; let t = dummy;
for (const v of a) { t.right = { val: v, left: null, right: null }; t = t.right; }
return dummy.right;
}