CareerCup

O(n) method....

void BalancePavanIdiotsTree(TreeNode *root)
{
	1) in order traverse and store in array A[]
        2) create balanced tree from A[] using divide and conquer (Pavan said this was easy)
}

Heapify the binary tree after getting into an array. O(n) solution.

Can we change the root of this tree ??

From Wikipedia: A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less...

So, in theory, we could maintain depth of the left and right subtrees in each node. At the root node, we will have the degree of imbalance between the left and right subtrees. If left subtree has more depth, then we move nodes from left to right subtree until the imbalance has been corrected to a difference of <= 1. Perhaps a recursive approach may be useful...

I have not coded this up, but will try now...just thought I will post the idea first.

1.) Flatten the input tree [inplace ]
2.) Use Binary search to create a balanced tree it just needs to be a tree and not a BST