Converting Normal BST to Balanced BST

Converting Normal BST to Balanced BST

Converting a normal Binary Search Tree (BST) to a Balanced BST involves reorganizing the nodes in such a way that the resulting tree is balanced, meaning the height of the left and right subtrees is approximately equal. There are multiple approaches to achieve this conversion.

A binary tree is considered balanced if the difference in height between its left and right subtrees (also known as the balance factor) is at most 1 for every node in the tree.

Example

A binary tree is considered balanced if the difference in height between its left and right subtrees (also known as the balance factor) is at most 1 for every node in the tree.

In the resulting Balanced BST, the heights of the left and right subtrees are equal, and it satisfies the property of a Balanced BST.

The heights of the left and right subtrees of each node after balancing are as follows for root node 2:

Height of node 2: Left subtree height = 1, Right subtree height = 2 (Difference = 1)

Height of node 1: Left subtree height = 0, Right subtree height = 0 (Difference = 0)

Height of node 4: Left subtree height = 0, Right subtree height = 0 (Difference = 0)

Height of node 3: Left subtree height = 0, Right subtree height = 1 (Difference = 1)


In this case, the difference in height between the left and right subtrees of each node is at most 1, which satisfies the condition for a balanced tree.

Both Cases are Correct