Balance a Binary Search Tree
Balance a Binary Search Tree is a medium trees & bst problem solved with the bst basics pattern.
The best approach, optimal (in-order nodes + relink), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from sorted values + new tree up.
Problem
You are given the root of a binary search tree. Return a height-balanced binary search tree that contains exactly the same values.
A binary tree is height-balanced when, for every node, the heights of its left and right subtrees differ by at most 1. If more than one balanced tree is possible, any of them is accepted.
Examples
Example 1
- Input
root = [2, 1, 3, null, null, null, 4, null, 5]- Output
[3, 1, 4, null, 2, null, 5]- Why
- The right spine 2 -> 3 -> 4 -> 5 makes the tree 4 levels deep. Rooting at the middle value 3 gives a tree of height 3 where no node's subtrees differ by more than 1. Other balanced shapes, such as [3, 2, 4, 1, null, null, 5], are accepted too.
Example 2
- Input
root = [9, 6, null, 4, null, 1]- Output
[4, 1, 6, null, null, null, 9]- Why
- A left-leaning chain of four values. Rooting at 4 leaves 1 on the left and 6, 9 on the right; [6, 4, 9, 1] would be just as valid.
Example 3
- Input
root = [5, 3, 8]- Output
[5, 3, 8]- Why
- The tree is already balanced, so returning it as it is works.
Constraints
- The tree has
1to10^4nodes. 1 <= Node.val <= 10^5- The input is a valid binary search tree with distinct values.
- Any height-balanced BST with exactly the same values is accepted.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Sorted values + new tree | O(n) | O(n) |
| Optimal (in-order nodes + relink) | O(n) | O(n) |
1Sorted values + new tree
O(n)Each node is visited once by the traversal and created once by the build.O(n)The value list, the traversal stack and n new nodes; the build recursion is only O(log n) deep.Read the values in sorted order with an in-order traversal (done iteratively, because the input can be a long chain). Then build a fresh tree: the middle value becomes the root, the left half builds the left subtree and the right half the right subtree. Splitting in the middle keeps both sides within one node of each other at every level.
- Iterative in-order traversal with a stack; append each value to a list.
- build(lo, hi): if lo > hi return null; mid = (lo + hi) / 2; create a node for vals[mid] and build its children from [lo, mid - 1] and [mid + 1, hi].
- Return build(0, n - 1).
class Solution {
public TreeNode balanceBST(TreeNode root) {
List<Integer> vals = new ArrayList<>();
Deque<TreeNode> st = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !st.isEmpty()) {
while (cur != null) {
st.push(cur);
cur = cur.left;
}
cur = st.pop();
vals.add(cur.val);
cur = cur.right;
}
return build(vals, 0, vals.size() - 1);
}
private TreeNode build(List<Integer> vals, int lo, int hi) {
if (lo > hi) return null;
int mid = (lo + hi) >>> 1;
TreeNode node = new TreeNode(vals.get(mid));
node.left = build(vals, lo, mid - 1);
node.right = build(vals, mid + 1, hi);
return node;
}
}class Solution:
def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
vals = []
st = []
cur = root
while cur or st:
while cur:
st.append(cur)
cur = cur.left
cur = st.pop()
vals.append(cur.val)
cur = cur.right
def build(lo: int, hi: int) -> Optional[TreeNode]:
if lo > hi:
return None
mid = (lo + hi) // 2
node = TreeNode(vals[mid])
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(vals) - 1)class Solution {
public:
TreeNode* balanceBST(TreeNode* root) {
vector<int> vals;
vector<TreeNode*> st;
TreeNode* cur = root;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push_back(cur);
cur = cur->left;
}
cur = st.back();
st.pop_back();
vals.push_back(cur->val);
cur = cur->right;
}
return build(vals, 0, (int)vals.size() - 1);
}
private:
TreeNode* build(const vector<int>& vals, int lo, int hi) {
if (lo > hi) return nullptr;
int mid = lo + (hi - lo) / 2;
TreeNode* node = new TreeNode(vals[mid]);
node->left = build(vals, lo, mid - 1);
node->right = build(vals, mid + 1, hi);
return node;
}
};function balanceBST(root) {
const vals = [];
const st = [];
let cur = root;
while (cur !== null || st.length > 0) {
while (cur !== null) {
st.push(cur);
cur = cur.left;
}
cur = st.pop();
vals.push(cur.val);
cur = cur.right;
}
const build = (lo, hi) => {
if (lo > hi) return null;
const mid = (lo + hi) >> 1;
const node = new TreeNode(vals[mid]);
node.left = build(lo, mid - 1);
node.right = build(mid + 1, hi);
return node;
};
return build(0, vals.length - 1);
}2Optimal (in-order nodes + relink)
O(n)One traversal and one relinking pass.O(n)The list of n node references and the traversal stack; no new nodes are created.Same divide-at-the-middle idea, but collect the node objects themselves instead of their values and rewire their child pointers. No node is allocated, and the original nodes end up forming the balanced tree.
- Iterative in-order traversal; append each node to a list.
- build(lo, hi): if lo > hi return null; node = nodes[mid]; node.left = build(lo, mid - 1); node.right = build(mid + 1, hi); return node.
- Return build(0, n - 1).
class Solution {
public TreeNode balanceBST(TreeNode root) {
List<TreeNode> nodes = new ArrayList<>();
Deque<TreeNode> st = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !st.isEmpty()) {
while (cur != null) {
st.push(cur);
cur = cur.left;
}
cur = st.pop();
nodes.add(cur);
cur = cur.right;
}
return build(nodes, 0, nodes.size() - 1);
}
private TreeNode build(List<TreeNode> nodes, int lo, int hi) {
if (lo > hi) return null;
int mid = (lo + hi) >>> 1;
TreeNode node = nodes.get(mid);
node.left = build(nodes, lo, mid - 1);
node.right = build(nodes, mid + 1, hi);
return node;
}
}class Solution:
def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
nodes = []
st = []
cur = root
while cur or st:
while cur:
st.append(cur)
cur = cur.left
cur = st.pop()
nodes.append(cur)
cur = cur.right
def build(lo: int, hi: int) -> Optional[TreeNode]:
if lo > hi:
return None
mid = (lo + hi) // 2
node = nodes[mid]
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(nodes) - 1)class Solution {
public:
TreeNode* balanceBST(TreeNode* root) {
vector<TreeNode*> nodes, st;
TreeNode* cur = root;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push_back(cur);
cur = cur->left;
}
cur = st.back();
st.pop_back();
nodes.push_back(cur);
cur = cur->right;
}
return build(nodes, 0, (int)nodes.size() - 1);
}
private:
TreeNode* build(vector<TreeNode*>& nodes, int lo, int hi) {
if (lo > hi) return nullptr;
int mid = lo + (hi - lo) / 2;
TreeNode* node = nodes[mid];
node->left = build(nodes, lo, mid - 1);
node->right = build(nodes, mid + 1, hi);
return node;
}
};function balanceBST(root) {
const nodes = [];
const st = [];
let cur = root;
while (cur !== null || st.length > 0) {
while (cur !== null) {
st.push(cur);
cur = cur.left;
}
cur = st.pop();
nodes.push(cur);
cur = cur.right;
}
const build = (lo, hi) => {
if (lo > hi) return null;
const mid = (lo + hi) >> 1;
const node = nodes[mid];
node.left = build(lo, mid - 1);
node.right = build(mid + 1, hi);
return node;
};
return build(0, nodes.length - 1);
}Edge cases to test
- A single node
- A tree that is already balanced
- A completely skewed tree (a linked list leaning left or right): avoid deep recursion over it
- Node counts that are one less than, equal to or one more than a power of two
Hints
Hint 1
An in-order traversal of a BST gives its values in sorted order.
Hint 2
From a sorted list, picking the middle element as the root and recursing on both halves always gives a height-balanced tree.
Hint 3
You do not need new nodes: collect the existing nodes in order and just rewire their left and right pointers.
FAQ
What is the best time complexity for Balance a Binary Search Tree?
Optimal (in-order nodes + relink) runs in O(n) time and O(n) extra space. One traversal and one relinking pass.
Which pattern does Balance a Binary Search Tree use?
It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.
Is there a brute force solution for Balance a Binary Search Tree?
Yes. Sorted values + new tree takes O(n) time and O(n) space. Read the values in sorted order with an in-order traversal (done iteratively, because the input can be a long chain).
Which edge cases should I test for Balance a Binary Search Tree?
A single node; A tree that is already balanced; A completely skewed tree (a linked list leaning left or right): avoid deep recursion over it; Node counts that are one less than, equal to or one more than a power of two.