You have been given a binary search tree of integers with ‘N’ nodes. Your task is to convert it into a balanced BST with the minimum height possible.
A binary search tree (BST) is a binary tree data structure that has the following properties.
• The left subtree of a node contains only nodes with data less than the node’s data. • The right subtree of a node contains only nodes with data greater than the node’s data. • Both the left and right subtrees must also be binary search trees.
A Balanced BST is defined as a BST, in which the height of two subtrees of every node differs no more than 1.
For the given BST:
The modified BST will be:
Sample output 1:
1 10 6 -1 4 -1 -1 -1
Explanation of Sample output 1:
4 6 10
The tree can be represented as follows:
After converting this tree to balanced BST. It will look like this:
Sample Input 2:
The inorder traversal of the modified tree will be 4 6 10. Since the inorder is sorted. Hence, it is a valid BST.
Sample output 2:
2 10 5 -1 -1 -1 20 -1 -1
5 10 20