Python 1382.py
class Solution:
def balanceBST(self, root: TreeNode) -> TreeNode:
flat = []
# in-order walk
def flatten(node):
if node:
flatten(node.left)
flat.append(node.val)
flatten(node.right)
def balance(left, right):
# invalid range
if left > right:
return None
# leaf
if left == right:
return TreeNode(flat[left])
# for performance reasons: let's process these easy cases explicitly
if left == right + 1:
return TreeNode(flat[left], None, TreeNode(flat[right]))
if left == right + 2:
return TreeNode(flat[left + 1], TreeNode(flat[left]), TreeNode(flat[right]))
# general case (can handle the two cases above as well)
mid = (left + right) // 2
return TreeNode(flat[mid], balance(left, mid - 1), \
balance(mid + 1, right))
flatten(root)
return balance(0, len(flat) - 1)
Difficulty
and has an acceptance rate of about 86% (400k+ submissions).
Typical patterns to solve this problem:
- Binary Search Tree
- Binary Tree
- Depth First Search
- Divide And Conquer
- Greedy
- Tree
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The implementation converts an arbitrary binary search tree into a height-balanced binary search tree. It first extracts the node values in sorted order using an in-order traversal, stores them in a list, and then recursively builds a new tree by selecting the middle element of each sub-range as the root. The result is a balanced tree where the depths of left and right subtrees differ by at most one.
Key Steps
The first phase walks the original tree in order and collects the values.
flat = []
def flatten(node):
if node:
flatten(node.left)
flat.append(node.val)
flatten(node.right)
flatten(root)
After the list flat holds the sorted values, the second phase constructs the balanced tree.
def balance(left, right):
if left > right:
return None
if left == right:
return TreeNode(flat[left])
if left == right + 1:
return TreeNode(flat[left], None, TreeNode(flat[right]))
if left == right + 2:
return TreeNode(flat[left + 1], TreeNode(flat[left]), TreeNode(flat[right]))
mid = (left + right) // 2
return TreeNode(
flat[mid],
balance(left, mid - 1),
balance(mid + 1, right)
)
return balance(0, len(flat) - 1)
The balance function receives the inclusive indices of the current sub-range and returns the root of the subtree built from that range.
Edge Cases Handled
When the sub-range is empty (left > right) the function returns None, correctly representing an absent child.
If the sub-range contains a single element (left == right) a leaf node is created directly from that value.
Two-element ranges (left == right + 1) are turned into a node with the larger value as the root and the smaller value as the right child, preserving the BST ordering while avoiding extra recursion.
Three-element ranges (left == right + 2) are built with the middle value as the root, the smallest as the left child, and the largest as the right child, again sidestepping deeper recursive calls.
These explicit branches ensure that the algorithm gracefully handles the smallest possible intervals without falling into infinite recursion or incorrect tree shapes.
Performance Optimizations
The code reduces recursion depth for the smallest intervals by handling one-, two-, and three-element ranges explicitly. This avoids the overhead of additional function calls for cases that can be resolved with a single node construction.
Using integer division to compute the midpoint (mid = (left + right) // 2) guarantees a deterministic split and prevents the creation of unbalanced sub-trees due to rounding errors.
Storing the sorted values in a plain Python list (flat) enables O(1) index access during the reconstruction phase, allowing the algorithm to reuse the same memory buffer without allocating new containers for each recursive step.
Overall, the approach combines a linear-time traversal to flatten the tree with a divide-and-conquer reconstruction that leverages in-place data and targeted base-case handling to achieve efficient balancing.
ELI5 - Simplified Explanation
Imagine you have a big pile of numbered building blocks that are connected in a messy, twisty tree shape. The first part of this code is like a little toy car that travels all the way through the tree to pick up every single block. It puts them in a straight line on the floor, all sorted from the smallest number to the biggest number.
Once the blocks are in a nice, neat line, it is time to build a new tree. The code looks for the block sitting right in the middle of the line to become the new top of the tree. This is a smart choice because it makes sure the left side and the right side have about the same number of blocks. Then, it looks at the middle of the remaining pieces for each side and puts those under the top one. It keeps doing this over and over again, like building a perfectly symmetrical tower, until all the blocks are back in a tree shape that stands up straight and tall without leaning to one side.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||
| WalkCCC | C++ | Java | Python | ||||||
| leetcode.ca | C++ | Java | Go | Python | TS | ||||
| Progiez | C++ | Java | Python | ||||||
| github | BigEggStudy | C# | |||||||
| black-shadows | C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| fartem | Ruby | ||||||||
| fsq | C++ | ||||||||
| JoshCrozier | JS | ||||||||
| keineahnung2345 | C++ | ||||||||
| lzl124631x | C++ | ||||||||
| MacJim | C++ | ||||||||
| varunu28 | Java | ||||||||
| withaarzoo | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | ||||||||
| Progiez | C++, Java, Python | ||||||||
| BigEggStudy | C# | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| fartem | Ruby | ||||||||
| fsq | C++ | ||||||||
| JoshCrozier | JavaScript | ||||||||
| keineahnung2345 | C++ | ||||||||
| lzl124631x | C++ | ||||||||
| MacJim | C++ | ||||||||
| varunu28 | Java | ||||||||
| withaarzoo | C++ |
Videos
Solved On The Same Day
- problem 2558: Take Gifts From the Richest Pile
- problem 395: Longest Substring with At Least K Repeating Characters
- problem 932: Beautiful Array
- problem 1424: Diagonal Traverse II
- problem 2406: Divide Intervals Into Minimum Number of Groups
- problem 2593: Find Score of an Array After Marking All Elements
- problem 2611: Mice and Cheese
- problem 2679: Sum in a Matrix
- problem 493: Reverse Pairs
- problem 2551: Put Marbles in Bags
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality