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.

Description Hints 2 Solution Video 12:23

1382. Balance a Binary Search Tree

Medium86.3% acceptance5 companies

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, 10⁴].
1 <= Node.val <= 10⁵

Asked at 5 companies

Amazon Microsoft Meta Bloomberg

Google

Topics

Hints open one at a time

Hint 1

Convert the tree to a sorted array using an in-order traversal.

Hint 2

Construct a new balanced tree from the sorted array recursively.

12:23

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,null,2,null,3,null,4]

Input

[2,1,3]

Your code is saved on this device.Solution