Similar Problems
Similar Problems not available
Balance A Binary Search Tree  Leetcode Solution
LeetCode: Balance A Binary Search Tree Leetcode Solution
Difficulty: Medium
Topics: greedy binarysearchtree depthfirstsearch tree binarytree
Problem statement:
Given a binary search tree, return a balanced binary search tree with the same node values.
A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.
If there is more than one answer, return any of them.
Solution:
The problem asks us to balance an unbalanced binary search tree while keeping its node values the same. We can solve this problem by following three steps:

Traverse the binary search tree and store the values of all its nodes in a sorted array using inorder traversal. This will result in a sorted array of all the node values.

Build a balanced binary search tree from the sorted array. We can do this by recursively selecting the middle element of the array and making it the root of the tree. Then, we can recursively build the left and the right subtrees of the root using the elements to the left and right of the middle element in the array.

Return the root of the balanced binary search tree.
Below is the implementation of the above steps:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) > TreeNode:
"""
Build a balanced binary search tree from a sorted array
"""
if not nums:
return None
middle = len(nums) // 2
root = TreeNode(nums[middle])
root.left = self.sortedArrayToBST(nums[:middle])
root.right = self.sortedArrayToBST(nums[middle+1:])
return root
def balanceBST(self, root: TreeNode) > TreeNode:
"""
Balance a binary search tree
"""
# Traverse the binary search tree and store its node values in a sorted array
def inorderTraversal(node):
if not node:
return []
return inorderTraversal(node.left) + [node.val] + inorderTraversal(node.right)
nums = inorderTraversal(root)
# Build a balanced binary search tree from the sorted array
return self.sortedArrayToBST(nums)
In the balanceBST
function, we first traverse the input binary search tree using inorder traversal and store its node values in a sorted array nums
. Then, we pass nums
to the sortedArrayToBST
function which builds a balanced binary search tree using the middle element as the root of the current subtree. Finally, we return the root of the balanced binary search tree.
Time complexity: The time complexity of the above solution is O(n log n) where n is the number of nodes in the binary search tree. The inorder traversal takes O(n) time and building a balanced binary search tree from a sorted array takes O(log n) time. Therefore total time complexity will be O(n log n).
Space complexity: The space complexity of the above solution is O(n) because we are storing all the node values in a sorted array. The recursive function calls will take additional space, but it will be O(log n) due to the balanced nature of the binary search tree. Therefore, the total space complexity will be O(n + log n) which can be simplified to O(n).
Balance A Binary Search Tree Solution Code
1