Problem 1382

Abstract / Summary

Given an unbalanced binary search tree return a balanced binary search tree with the same node values.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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)
31 lines | 1131 bytes | submitted November 22, 2023 | GitHub   22% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

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
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.67 | σ = 1.63

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
27 links | 16 authors | 8 languages

Videos

10 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

11 solutions   November 22, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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