Binary Search TreesProblem 9 of 22
Convert Binary tree into BST
Problem Statement
Given a Binary Tree, convert it to a Binary Search Tree while maintaining the original tree structure. Only the values should be rearranged, not the structure.
Example:
Input Binary Tree: Output BST:
10 8
/ \ / \
2 7 4 10
/ \ / \
8 4 2 7
Inorder of input: [8, 2, 4, 10, 7]
Inorder of BST: [2, 4, 7, 8, 10]
Approach 1: Brute Force (Extract, Sort, Rebuild Entire Tree)
Intuition
Extract all values, sort them, and rebuild a completely new BST. This doesn't preserve the original structure but gives a balanced BST.
Algorithm
- Extract all values from the binary tree
- Sort the values
- Build a balanced BST from sorted array
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void extractValues(TreeNode root, List<Integer> values) {
if (root == null) return;
extractValues(root.left, values);
values.add(root.val);
extractValues(root.right, values);
}
private TreeNode buildBST(List<Integer> values, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(values.get(mid));
root.left = buildBST(values, left, mid - 1);
root.right = buildBST(values, mid + 1, right);
return root;
}
// This creates a NEW balanced BST, doesn't preserve structure
public TreeNode convertToBSTBruteForce(TreeNode root) {
List<Integer> values = new ArrayList<>();
extractValues(root, values);
Collections.sort(values);
return buildBST(values, 0, values.size() - 1);
}
}Complexity Analysis
- Time Complexity: O(n log n) - Sorting dominates
- Space Complexity: O(n) - Storing values
Approach 2: Optimal (Preserve Structure - Inorder Replace)
Intuition
To preserve the original tree structure:
- Extract values and sort them
- Perform inorder traversal and replace values in sorted order
Since inorder traversal visits nodes in left-root-right order, replacing with sorted values gives BST property.
Algorithm
- Store inorder traversal (any traversal works for extraction)
- Sort the values
- Perform inorder traversal again, replacing each node's value with next sorted value
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int idx = 0;
private void extractValues(TreeNode root, List<Integer> values) {
if (root == null) return;
extractValues(root.left, values);
values.add(root.val);
extractValues(root.right, values);
}
private void replaceInorder(TreeNode root, List<Integer> sortedValues) {
if (root == null) return;
replaceInorder(root.left, sortedValues);
root.val = sortedValues.get(idx++);
replaceInorder(root.right, sortedValues);
}
public TreeNode convertToBST(TreeNode root) {
if (root == null) return null;
// Step 1: Extract all values
List<Integer> values = new ArrayList<>();
extractValues(root, values);
// Step 2: Sort values
Collections.sort(values);
// Step 3: Replace values in inorder
idx = 0;
replaceInorder(root, values);
return root;
}
}Complexity Analysis
- Time Complexity: O(n log n) - Sorting dominates
- Space Complexity: O(n) - Storing values + recursion stack
Approach 3: Alternative (Using Set for Sorted Storage)
Intuition
Use a set (or multiset for duplicates) to store values in sorted order during extraction itself.
Algorithm
- Extract values into a set/multiset (auto-sorted)
- Perform inorder traversal replacing with set values
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private Iterator<Integer> iterator;
private void extractValues(TreeNode root, TreeSet<Integer> values) {
if (root == null) return;
values.add(root.val);
extractValues(root.left, values);
extractValues(root.right, values);
}
private void replaceInorder(TreeNode root) {
if (root == null) return;
replaceInorder(root.left);
root.val = iterator.next();
replaceInorder(root.right);
}
// Note: TreeSet doesn't allow duplicates, use ArrayList + sort for duplicates
public TreeNode convertToBSTUsingSet(TreeNode root) {
if (root == null) return null;
TreeSet<Integer> values = new TreeSet<>();
extractValues(root, values);
iterator = values.iterator();
replaceInorder(root);
return root;
}
}Complexity Analysis
- Time Complexity: O(n log n) - Set insertion is O(log n)
- Space Complexity: O(n) - Storing values
Key Takeaways
- Two interpretations: Create new balanced BST vs preserve original structure
- Inorder key insight: Inorder traversal of BST is sorted
- Replace strategy: Sort values, replace during inorder traversal
- Structure preservation: Only values change, not the links
- This technique is used in many tree transformation problems
- Sorting is the bottleneck - O(n log n) is optimal
- The resulting BST may not be balanced (depends on original structure)