Convert a normal BST to Balanced BST | Java 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 program to test the above functions ; Constructed skewed binary tree is 10 / 8 / 7 / 6 / 5
import java . util . * ; class Node { int data ; Node left , right ; public Node ( int data ) { this . data = data ; left = right = null ; } } class BinaryTree { Node root ; void storeBSTNodes ( Node root , Vector < Node > nodes ) { if ( root == null ) return ; storeBSTNodes ( root . left , nodes ) ; nodes . add ( root ) ; storeBSTNodes ( root . right , nodes ) ; } Node buildTreeUtil ( Vector < Node > nodes , int start , int end ) { if ( start > end ) return null ; int mid = ( start + end ) / 2 ; Node node = nodes . get ( mid ) ; node . left = buildTreeUtil ( nodes , start , mid - 1 ) ; node . right = buildTreeUtil ( nodes , mid + 1 , end ) ; return node ; } Node buildTree ( Node root ) { Vector < Node > nodes = new Vector < Node > ( ) ; storeBSTNodes ( root , nodes ) ; int n = nodes . size ( ) ; return buildTreeUtil ( nodes , 0 , n - 1 ) ; } void preOrder ( Node node ) { if ( node == null ) return ; System . out . print ( node . data + " ▁ " ) ; preOrder ( node . left ) ; preOrder ( node . right ) ; } public static void main ( String [ ] args ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 10 ) ; tree . root . left = new Node ( 8 ) ; tree . root . left . left = new Node ( 7 ) ; tree . root . left . left . left = new Node ( 6 ) ; tree . root . left . left . left . left = new Node ( 5 ) ; tree . root = tree . buildTree ( tree . root ) ; System . out . println ( " Preorder ▁ traversal ▁ of ▁ balanced ▁ BST ▁ is ▁ : " ) ; tree . preOrder ( tree . root ) ; } }