Balance a Binary Search Tree solution and explanation
Google
9 more videos on this problem
Balance a Binary Search Tree | Leetcode #1382Techdose · 12:23 · 19K views
Balance a Binary Search Tree | Simple Explanation | Leetcode 1382 | codestorywithMIKcodestorywithMIK · 14:11 · 17K views
1382, 108 Balance a Binary Search Tree | Day-Stout-Warren (DSW) Algorithm | In-Place BalancingAryan Mittal · 34:49 · 6K views
Balance a Binary Search Tree - LeetCode 1382 - JavaScriptAlgoJS · 4:48 · 1K views
Balance a Binary Search Tree | LeetCode 1382 | Recursive ReconstructionSanyam IIT Guwahati · 14:01 · 1K views
1382. Balance a Binary Search Tree | Leetcode Daily - PythonLeetcode Daily · 9:09 · 988 views
Balance a Binary Search Tree - Leetcode 1382 - Swift SolutionAndrey Tech · 6:26 · 804 views
Daily Leetcode #2141: Feb 09, 2026 - 1382. Balance a Binary Search TreeProgramming Live with Larry · 9:49 · 622 views
Balance a Binary Search Tree (Leetcode 1382)Coding Interviews · 16:07 · 479 views
Balance a Binary Search Tree | Leetcode 1382 | Java Code | Developer CoderDeveloper Coder · 12:14 · 218 views
The problem
Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them.
A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.
Example 1:
Input: root = [1,null,2,null,3,null,4,null,null] Output: [2,1,3,null,null,null,4] Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.
Example 2:
Input: root = [2,1,3] Output: [2,1,3]
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. 1 <= Node.val <= 105
Approach overview
Problem Overview: You receive the root of a binary search tree that may be heavily skewed. The task is to return a height-balanced BST containing the same node values. A balanced tree keeps the height difference between left and right subtrees small, ensuring operations like search and insertion remain efficient.
Approach 1: In-order Traversal and Rebuilding (O(n) time, O(n) space)
A binary search tree has one critical property: an in-order traversal visits nodes in sorted order. Traverse the tree using DFS and store all node values in an array. Once you have the sorted list, build a new balanced BST by repeatedly selecting the middle element as the root. Recursively construct the left subtree from the left half and the right subtree from the right half. This guarantees minimal height because each level splits the data roughly in half. Time complexity is O(n) since every node is visited once and reconstructed once. Space complexity is O(n) for the array plus recursion stack.
This approach is widely used because it is simple and reliable. It converts the structural problem of balancing a tree into a sorted-array construction problem. The traversal step relies on Depth-First Search, while the reconstruction mirrors classic balanced BST creation techniques from a sorted list.
Approach 2: Divide-And-Conquer Direct Construction (O(n) time, O(n) space)
The second approach still relies on the sorted nature of BST traversal but emphasizes the Divide and Conquer pattern more explicitly. First perform an in-order traversal to collect nodes. Instead of only storing values, you can reuse the node objects themselves. Recursively choose the middle node as the root, attach the left half as the left subtree and the right half as the right subtree. Each recursive step splits the array into two halves, ensuring the resulting tree remains balanced.
This technique ensures each node participates in exactly one recursive construction step. Time complexity remains O(n). Space complexity is O(n) due to storing the traversal and recursion depth. Because the algorithm repeatedly divides the sorted sequence, it naturally produces a balanced structure.
Both approaches rely on the core property of a Binary Search Tree: sorted order from in-order traversal. Once the values are sorted, building a balanced BST becomes a deterministic recursive process.
Recommended for interviews: The in-order traversal plus rebuild approach is the expected solution. It demonstrates understanding of BST properties and balanced tree construction while keeping the implementation clean. Interviewers often accept both variants, but showing the sorted-array reconstruction pattern clearly signals strong grasp of tree traversal and divide-and-conquer thinking.
Approach 1: In-order Traversal and Rebuilding
This approach involves performing an in-order traversal of the binary search tree to collect its node values in sorted order. Since the values are sorted, we can then use the sorted list to construct a balanced binary search tree. The central idea is that the middle element of the sorted list becomes the root of the tree, and recursively the middle element of each sublist becomes the root of the subtrees, thereby ensuring balanced condition.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorder(self, root, nodes):
if root:
self.inorder(root.left, nodes)
nodes.append(root.val)
self.inorder(root.right, nodes)
def buildTree(self, nodes, start, end):
if start > end:
return None
mid = (start + end) // 2
node = TreeNode(nodes[mid])
node.left = self.buildTree(nodes, start, mid - 1)
node.right = self.buildTree(nodes, mid + 1, end)
return node
def balanceBST(self, root):
nodes = []
self.inorder(root, nodes)
return self.buildTree(nodes, 0, len(nodes) - 1)import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<Integer> nodes) {
if (root == null) return;
inorder(root.left, nodes);
nodes.add(root.val);
inorder(root.right, nodes);
}
private TreeNode buildTree(List<Integer> nodes, int start, int end) {
if (start > end) return null;
int mid = start + (end - start) / 2;
TreeNode node = new TreeNode(nodes.get(mid));
node.left = buildTree(nodes, start, mid - 1);
node.right = buildTree(nodes, mid + 1, end);
return node;
}
public TreeNode balanceBST(TreeNode root) {
List<Integer> nodes = new ArrayList<>();
inorder(root, nodes);
return buildTree(nodes, 0, nodes.size() - 1);
}
}#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorder(TreeNode* root, vector<int>& nodes) {
if (!root) return;
inorder(root->left, nodes);
nodes.push_back(root->val);
inorder(root->right, nodes);
}
TreeNode* buildTree(vector<int>& nodes, int start, int end) {
if (start > end) return nullptr;
int mid = start + (end - start) / 2;
TreeNode* node = new TreeNode(nodes[mid]);
node->left = buildTree(nodes, start, mid - 1);
node->right = buildTree(nodes, mid + 1, end);
return node;
}
TreeNode* balanceBST(TreeNode* root) {
vector<int> nodes;
inorder(root, nodes);
return buildTree(nodes, 0, nodes.size() - 1);
}class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function inorder(root, nodes) {
if (!root) return;
inorder(root.left, nodes);
nodes.push(root.val);
inorder(root.right, nodes);
}
function buildTree(nodes, start, end) {
if (start > end) return null;
const mid = Math.floor((start + end) / 2);
const node = new TreeNode(nodes[mid]);
node.left = buildTree(nodes, start, mid - 1);
node.right = buildTree(nodes, mid + 1, end);
return node;
}
function balanceBST(root) {
const nodes = [];
inorder(root, nodes);
return buildTree(nodes, 0, nodes.length - 1);
}#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void inorder(struct TreeNode* root, int* arr, int* size) {
if (!root) return;
inorder(root->left, arr, size);
arr[(*size)++] = root->val;
inorder(root->right, arr, size);
}
struct TreeNode* buildTree(int* arr, int start, int end) {
if (start > end) return NULL;
int mid = start + (end - start) / 2;
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = arr[mid];
node->left = buildTree(arr, start, mid - 1);
node->right = buildTree(arr, mid + 1, end);
return node;
}
struct TreeNode* balanceBST(struct TreeNode* root) {
int arr[10000], size = 0;
inorder(root, arr, &size);
return buildTree(arr, 0, size - 1);
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private void Inorder(TreeNode root, List<int> nodes) {
if (root == null) return;
Inorder(root.left, nodes);
nodes.Add(root.val);
Inorder(root.right, nodes);
}
private TreeNode BuildTree(List<int> nodes, int start, int end) {
if (start > end) return null;
int mid = start + (end - start) / 2;
TreeNode node = new TreeNode(nodes[mid]);
node.left = BuildTree(nodes, start, mid - 1);
node.right = BuildTree(nodes, mid + 1, end);
return node;
}
public TreeNode BalanceBST(TreeNode root) {
List<int> nodes = new List<int>();
Inorder(root, nodes);
return BuildTree(nodes, 0, nodes.Count - 1);
}
}The Python solution is structured similarly, with an inorder method to gather node values, and a buildTree method to recursively construct the balanced BST from the sorted values.
Time Complexity: O(n), achieving efficient traversal and reconstruction process.
Space Complexity: O(n), needed for list storage of node elements.
Approach 2: Divide-And-Conquer Direct Construction
This alternative approach aims to build a balanced BST directly from the given BST by using a divide-and-conquer strategy. The process involves using in-order traversal to fetch node values, converting it to a sorted array, and recursively constructing the entire balanced tree directly. While the initial step is similar, this approach focuses on minimizing operations by targeting balanced construction upfront.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorder(self, root, nodes):
if root:
self.inorder(root.left, nodes)
nodes.append(root.val)
self.inorder(root.right, nodes)
def createBalancedTree(self, nodes, start, end):
if start > end:
return None
mid = (start + end) // 2
node = TreeNode(nodes[mid])
node.left = self.createBalancedTree(nodes, start, mid - 1)
node.right = self.createBalancedTree(nodes, mid + 1, end)
return node
def balanceBST(self, root):
nodes = []
self.inorder(root, nodes)
return self.createBalancedTree(nodes, 0, len(nodes) - 1)import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<Integer> nodes) {
if (root == null) return;
inorder(root.left, nodes);
nodes.add(root.val);
inorder(root.right, nodes);
}
private TreeNode createBalancedTree(List<Integer> nodes, int start, int end) {
if (start > end) return null;
int mid = start + (end - start) / 2;
TreeNode node = new TreeNode(nodes.get(mid));
node.left = createBalancedTree(nodes, start, mid - 1);
node.right = createBalancedTree(nodes, mid + 1, end);
return node;
}
public TreeNode balanceBST(TreeNode root) {
List<Integer> nodes = new ArrayList<>();
inorder(root, nodes);
return createBalancedTree(nodes, 0, nodes.size() - 1);
}
}#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorder(TreeNode* root, vector<int>& nodes) {
if (!root) return;
inorder(root->left, nodes);
nodes.push_back(root->val);
inorder(root->right, nodes);
}
TreeNode* createBalancedTree(vector<int>& nodes, int start, int end) {
if (start > end) return nullptr;
int mid = (start + end) / 2;
TreeNode* node = new TreeNode(nodes[mid]);
node->left = createBalancedTree(nodes, start, mid - 1);
node->right = createBalancedTree(nodes, mid + 1, end);
return node;
}
TreeNode* balanceBST(TreeNode* root) {
vector<int> nodes;
inorder(root, nodes);
return createBalancedTree(nodes, 0, nodes.size() - 1);
}class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function inorder(root, nodes) {
if (!root) return;
inorder(root.left, nodes);
nodes.push(root.val);
inorder(root.right, nodes);
}
function createBalancedTree(nodes, start, end) {
if (start > end) return null;
const mid = Math.floor((start + end) / 2);
const node = new TreeNode(nodes[mid]);
node.left = createBalancedTree(nodes, start, mid - 1);
node.right = createBalancedTree(nodes, mid + 1, end);
return node;
}
function balanceBST(root) {
const nodes = [];
inorder(root, nodes);
return createBalancedTree(nodes, 0, nodes.length - 1);
}#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void inorder(struct TreeNode* root, int* arr, int* size) {
if (!root) return;
inorder(root->left, arr, size);
arr[(*size)++] = root->val;
inorder(root->right, arr, size);
}
struct TreeNode* createBalancedTree(int* arr, int start, int end) {
if (start > end) return NULL;
int mid = (start + end) / 2;
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = arr[mid];
root->left = createBalancedTree(arr, start, mid - 1);
root->right = createBalancedTree(arr, mid + 1, end);
return root;
}
struct TreeNode* balanceBST(struct TreeNode* root) {
int arr[10000], size = 0;
inorder(root, arr, &size);
return createBalancedTree(arr, 0, size - 1);
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private void Inorder(TreeNode root, List<int> nodes) {
if (root == null) return;
Inorder(root.left, nodes);
nodes.Add(root.val);
Inorder(root.right, nodes);
}
private TreeNode CreateBalancedTree(List<int> nodes, int start, int end) {
if (start > end) return null;
int mid = start + (end - start) / 2;
TreeNode node = new TreeNode(nodes[mid]);
node.left = CreateBalancedTree(nodes, start, mid - 1);
node.right = CreateBalancedTree(nodes, mid + 1, end);
return node;
}
public TreeNode BalanceBST(TreeNode root) {
List<int> nodes = new List<int>();
Inorder(root, nodes);
return CreateBalancedTree(nodes, 0, nodes.Count - 1);
}
}The Python code brings forth similar functional elements. In-order traversal supports sorted collection, forwarded to createBalancedTree for balanced structural outcomes guided by midpoints.
Time Complexity: O(n) defined by traversal and BST rebuild.
Space Complexity: O(n), demanding list memory for nodes.
Approach 3: In-order Traversal + Construct Balanced Binary Search Tree
Since the original tree is a binary search tree, we can save the result of the in-order traversal in an array nums. Then we design a function build(i, j), which is used to construct a balanced binary search tree within the index range [i, j] in nums. The answer is build(0, |nums| - 1).
The execution logic of the function build(i, j) is as follows:
- If
i > j, then the balanced binary search tree is empty, return an empty node; - Otherwise, we take
mid = (i + j) / 2as the root node, then recursively build the left and right subtrees, and return the root node.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary search tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function balanceBST(root: TreeNode | null): TreeNode | null {
const nums: number[] = [];
const dfs = (root: TreeNode | null): void => {
if (root == null) {
return;
}
dfs(root.left);
nums.push(root.val);
dfs(root.right);
};
const build = (i: number, j: number): TreeNode | null => {
if (i > j) {
return null;
}
const mid: number = (i + j) >> 1;
const left: TreeNode | null = build(i, mid - 1);
const right: TreeNode | null = build(mid + 1, j);
return new TreeNode(nums[mid], left, right);
};
dfs(root);
return build(0, nums.length - 1);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func balanceBST(root *TreeNode) *TreeNode {
ans := []int{}
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
ans = append(ans, root.Val)
dfs(root.Right)
}
var build func(i, j int) *TreeNode
build = func(i, j int) *TreeNode {
if i > j {
return nil
}
mid := (i + j) >> 1
left := build(i, mid-1)
right := build(mid+1, j)
return &TreeNode{Val: ans[mid], Left: left, Right: right}
}
dfs(root)
return build(0, len(ans)-1)
}Complexity comparison
| Approach | Complexity |
|---|---|
| In-order Traversal and Rebuilding | Time Complexity: O(n), achieving efficient traversal and reconstruction process. |
| Divide-And-Conquer Direct Construction | Time Complexity: O(n) defined by traversal and BST rebuild. |
| In-order Traversal + Construct Balanced Binary Search Tree | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-order Traversal and Rebuilding | O(n) | O(n) | Most common approach. Easy to implement and guarantees a balanced BST using a sorted array. |
| Divide-and-Conquer Direct Construction | O(n) | O(n) | Preferred when emphasizing divide-and-conquer recursion or reusing node objects instead of values. |
Frequently asked questions
Is Balance a Binary Search Tree easy or hard?
Balance a Binary Search Tree is rated Medium difficulty on LeetCode. The logic becomes straightforward once you recognize that inorder traversal of a BST yields a sorted sequence that can be used to rebuild a balanced tree.
Balance a Binary Search Tree Python/Java solution
Python and Java implementations follow the same pattern: run an inorder DFS to collect sorted values, then recursively build the tree using the middle element as the root. This produces a balanced BST in O(n) time and works consistently across Python, Java, C++, and other languages.
How to solve Balance a Binary Search Tree in O(n)?
Perform an inorder traversal of the BST to collect all node values in sorted order. Then build a balanced BST by recursively selecting the middle element as the root and splitting the remaining elements into left and right halves. Each node is processed a constant number of times, leading to O(n) total time.
What is the best approach for Balance a Binary Search Tree?
The most common solution performs an inorder traversal to extract values in sorted order, then rebuilds the BST by choosing the middle element as the root recursively. This guarantees a height-balanced tree and runs in O(n) time with O(n) extra space. The approach is simple and commonly expected in coding interviews.
Is Balance a Binary Search Tree asked at Google/Amazon/Meta?
Balanced BST construction and tree restructuring problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variations often test understanding of BST properties, inorder traversal, and divide-and-conquer recursion.
What data structure is used in Balance a Binary Search Tree?
The core data structure is a Binary Search Tree. The solution typically uses an auxiliary array or list to store the inorder traversal, along with recursion to construct the balanced tree structure.
What is the time complexity of Balance a Binary Search Tree?
The optimal solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited once during inorder traversal and once during reconstruction. Space complexity is O(n) because the algorithm stores node values in an array and uses recursion.