Balanced BST AVL tree

1382. Balance a Binary Search Tree

Balance a Binary Search Tree - LeetCode

We can solve it by using the AVL tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        def storeBSTNodes(root,nodes): 
            # Base case 
            if not root: return
            # Store nodes in Inorder (which is sorted  
            # order for BST)  
            storeBSTNodes(root.left,nodes) 
            nodes.append(root) 
            storeBSTNodes(root.right,nodes) 
  
        # Recursive function to construct binary tree   
        def buildTreeUtil(nodes,start,end): 
            # base case  
            if start>end: return None
  
            # Get the middle element and make it root  
            mid=(start+end)//2
            node=nodes[mid] 
  
            # Using index in Inorder traversal, construct  
            # left and right subtress 
            node.left=buildTreeUtil(nodes,start,mid-1) 
            node.right=buildTreeUtil(nodes,mid+1,end) 
            return node 
  
        # This functions converts an unbalanced BST to  
        # a balanced BST 
        def buildTree(root): 
      
            # Store nodes of given BST in sorted order  
            nodes=[] 
            storeBSTNodes(root,nodes) 
  
            # Constucts BST from nodes[]  
            n=len(nodes) 
            return buildTreeUtil(nodes,0,n-1) 
        return buildTree(root)

Or do it in a more concise way

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        nodes = []
        
        def in_order_traverse(root):
            if root is None:return
            in_order_traverse(root.left)
            nodes.append(root)
            in_order_traverse(root.right)
            return nodes
        
        def build_balanced_tree(left, right):
            if left>right:return None
            mid = (left+right)//2
            root = nodes[mid]
            root.left = build_balanced_tree(left, mid-1)
            root.right = build_balanced_tree(mid+1, right)
            return root
        in_order_traverse(root)
        return build_balanced_tree(0, len(nodes)-1)

Actually the above solution is not using AVL tree idea. Will explore AVL tree later.