Convert a normal BST to Balanced BST | C # 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
using System ; using System . Collections . Generic ; public class Node { public int data ; public Node left , right ; public Node ( int data ) { this . data = data ; left = right = null ; } } public class BinaryTree { public Node root ; public virtual void storeBSTNodes ( Node root , List < Node > nodes ) { if ( root == null ) { return ; } storeBSTNodes ( root . left , nodes ) ; nodes . Add ( root ) ; storeBSTNodes ( root . right , nodes ) ; } public virtual Node buildTreeUtil ( List < Node > nodes , int start , int end ) { if ( start > end ) { return null ; } int mid = ( start + end ) / 2 ; Node node = nodes [ mid ] ; node . left = buildTreeUtil ( nodes , start , mid - 1 ) ; node . right = buildTreeUtil ( nodes , mid + 1 , end ) ; return node ; } public virtual Node buildTree ( Node root ) { List < Node > nodes = new List < Node > ( ) ; storeBSTNodes ( root , nodes ) ; int n = nodes . Count ; return buildTreeUtil ( nodes , 0 , n - 1 ) ; } public virtual void preOrder ( Node node ) { if ( node == null ) { return ; } Console . Write ( 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 ) ; Console . WriteLine ( " Preorder ▁ traversal ▁ of ▁ balanced ▁ BST ▁ is ▁ : " ) ; tree . preOrder ( tree . root ) ; } }