Convert a binary tree to a BST / balance a BST / flatten a BST to a sorted list
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]
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;}