1382.balance-a-binary-search-tree.md

1382. Balance a Binary Search Tree

Inorder

We can build the inorder traversal of the tree and then build a new tree from the inorder traversal.

private val list = mutableListOf<TreeNode>()

fun balanceBST(root: TreeNode?): TreeNode? {
    if (root == null) return null
    inorder(root)
    return build(0, list.size - 1)        
}

private fun inorder(root: TreeNode?) {
    if (root == null) return
    inorder(root.left)
    list.add(root)
    inorder(root.right)
}

private fun build(start: Int, end: Int): TreeNode? {
    if (start > end) return null
    val middle = start + (end - start) / 2
    val newRoot = list[middle]
    newRoot.left = build(start, middle - 1)
    newRoot.right = build(middle + 1, end)
    return newRoot
}

• Time Complexity: O(n)
• Space Complexity: O(n)