Convert a normal BST to Balanced BST | Python3 program to convert a left unbalanced BST to a balanced BST ; A binary tree node has data , pointer to left child and a pointer to right child ; This function traverse the skewed binary tree and stores its nodes pointers in vector nodes [ ] ; Base case ; Store nodes in Inorder ( which is sorted order for BST ) ; Recursive function to construct binary tree ; base case ; Get the middle element and make it root ; Using index in Inorder traversal , construct left and right subtress ; This functions converts an unbalanced BST to a balanced BST ; Store nodes of given BST in sorted order ; Constucts BST from nodes [ ] ; Function to do preorder traversal of tree ; Driver code ; Constructed skewed binary tree is 10 / 8 / 7 / 6 / 5
import sys NEW_LINE import math NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def storeBSTNodes ( root , nodes ) : NEW_LINE INDENT if not root : NEW_LINE INDENT return NEW_LINE DEDENT storeBSTNodes ( root . left , nodes ) NEW_LINE nodes . append ( root ) NEW_LINE storeBSTNodes ( root . right , nodes ) NEW_LINE DEDENT def buildTreeUtil ( nodes , start , end ) : NEW_LINE INDENT if start > end : NEW_LINE INDENT return None NEW_LINE DEDENT mid = ( start + end ) // 2 NEW_LINE node = nodes [ mid ] NEW_LINE node . left = buildTreeUtil ( nodes , start , mid - 1 ) NEW_LINE node . right = buildTreeUtil ( nodes , mid + 1 , end ) NEW_LINE return node NEW_LINE DEDENT def buildTree ( root ) : NEW_LINE INDENT nodes = [ ] NEW_LINE storeBSTNodes ( root , nodes ) NEW_LINE n = len ( nodes ) NEW_LINE return buildTreeUtil ( nodes , 0 , n - 1 ) NEW_LINE DEDENT def preOrder ( root ) : NEW_LINE INDENT if not root : NEW_LINE INDENT return NEW_LINE DEDENT print ( " { } ▁ " . format ( root . data ) , end = " " ) NEW_LINE preOrder ( root . left ) NEW_LINE preOrder ( root . right ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = Node ( 10 ) NEW_LINE root . left = Node ( 8 ) NEW_LINE root . left . left = Node ( 7 ) NEW_LINE root . left . left . left = Node ( 6 ) NEW_LINE root . left . left . left . left = Node ( 5 ) NEW_LINE root = buildTree ( root ) NEW_LINE print ( " Preorder ▁ traversal ▁ of ▁ balanced ▁ BST ▁ is ▁ : " ) NEW_LINE preOrder ( root ) NEW_LINE DEDENT