LC 1382 [M] Balance a Binary Search Tree - ALawliet/algorithms GitHub Wiki

1. inorder traversal to convert to sorted array
2. binary search to convert sorted array to BST

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        A = []
        
        def inorder(root):
            if not root: return
            inorder(root.left)
            A.append(root)
            inorder(root.right)
        
        def bst(l, r):
            if not l <= r: return None
            m = (l + r) // 2
            root = A[m]
            root.left = bst(l, m - 1)
            root.right = bst(m + 1, r)
            return root
        
        inorder(root)
        # A is the list of nodes in sorted order
    
        n = len(A)
        l = 0
        r = n - 1
        return bst(l, r)