Given an unbalanced Binary Search Tree (BST), the task is to convert it into a balanced BST in linear time and without using auxiliary space.
Examples:
Input: 5
/ \
1 10
\
20
\
35
Output: 20
/ \
5 35
/ \
1 10Input: 10
/
5
/
2
/
1
Output: 5
/ \
2 10
/
1
Approach: The algorithm used in this scenario is the Day-Stout-Warren algorithm. The balanced tree formed will be a complete binary tree. Follow the steps below for the implementation of the algorithm.
- Step 1: Convert the given BST into a linked list ( right-sided linked list ) using the concept of right rotations by means of inorder traversal. This form of BST is known as backbone or vine. the Runtime of this phase is linear and no extra space is required.
The function is coded in such a way that it does all the required right rotation to flatten the BST and at the end returns the number of nodes in BST. - Step 2: Calculate the height of BST in which all the levels will be completely filled using the formula h = log2(N+1) [N is the total number of nodes]. And using the height calculate the number of nodes that can be fitted in that height m = pow(2, h)-1. [h is height till which all the levels are fully filled with nodes]
The difference (diff) of N and m is the amount of nodes that will be there in last level of balanced complete binary tree. - The vine obtained in the first step is then left rotated diff amount of time from its root. The above modified tree is then left rotated m/2, m/4, m/8 . . . times until m is greater than 0 according to the algorithm
Illustrations:
Illustration-1: Here the given tree is a left skewed BST
Example-1
Illustration-2: Here it is a non-skewed but unbalanced BST
Example-2
Below is the implementation of the above approach.
C++
// C++ code to balance BST using DSW algorithm.#include <bits/stdc++.h>using namespace std;// Defining the structure for TreeNode.struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode() : val(0) , left(NULL) , right(NULL) { } TreeNode(int x) : val(x) , left(NULL) , right(NULL) { } TreeNode(int x, TreeNode* left, TreeNode* right) : val(x) , left(left) , right(right) { }};// Function to convert input BST // to right linked list// known as vine or backbone.int bstToVine(TreeNode* grand){ int count = 0; // Make tmp pointer to traverse // and right flatten the given BST. TreeNode* tmp = grand->right; // Traverse until tmp becomes NULL while (tmp) { // If left exist for node // pointed by tmp then // right rotate it. if (tmp->left) { TreeNode* oldTmp = tmp; tmp = tmp->left; oldTmp->left = tmp->right; tmp->right = oldTmp; grand->right = tmp; } // If left dont exists // add 1 to count and // traverse further right to // flatten remaining BST. else { count++; grand = tmp; tmp = tmp->right; } } return count;}// Function to compress given tree// with its root as grand->right.void compress(TreeNode* grand, int m){ // Make tmp pointer to traverse // and compress the given BST. TreeNode* tmp = grand->right; // Traverse and left-rotate root m times // to compress given vine form of BST. for (int i = 0; i < m; i++) { TreeNode* oldTmp = tmp; tmp = tmp->right; grand->right = tmp; oldTmp->right = tmp->left; tmp->left = oldTmp; grand = tmp; tmp = tmp->right; }}// Function to implement the algorithmTreeNode* balanceBST(TreeNode* root){ // create dummy node with value 0 TreeNode* grand = new TreeNode(0); // assign the right of dummy node as our input BST grand->right = root; // get the number of nodes in input BST and // simultaneously convert it into right linked list. int count = bstToVine(grand); // gets the height of tree in which all levels // are completely filled. int h = log2(count + 1); // get number of nodes until second last level int m = pow(2, h) - 1; // Left rotate for excess nodes at last level compress(grand, count - m); // Left rotation till m becomes 0 // Step is done as mentioned in algo to // make BST balanced. for (m = m / 2; m > 0; m /= 2) { compress(grand, m); } // return the balanced tree return grand->right;}// Function to print preorder traversal// of Binary tree.void preorderTraversal(TreeNode* root){ if (!root) return; cout << root->val << " "; preorderTraversal(root->left); preorderTraversal(root->right); return;}// Driver codeint main(){ TreeNode* root = new TreeNode(10); root->left = new TreeNode(5); root->left->left = new TreeNode(2); root->left->left->left = new TreeNode(1); // Function call to implement // Day-Stout-Warren algorithm root = balanceBST(root); // To print the preorder traversal of BST preorderTraversal(root); return 0;} |
Java
// Java code to balance BST using DSW algorithm.public class DayStout { // Defining the structure for TreeNode. static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } } // Function to convert input BST // to right linked list // known as vine or backbone. static int bstToVine(TreeNode grand) { int count = 0; // Make tmp pointer to traverse // and right flatten the given BST. TreeNode tmp = grand.right; // Traverse until tmp becomes NULL while (tmp != null) { // If left exist for node // pointed by tmp then // right rotate it. if (tmp.left != null) { TreeNode oldTmp = tmp; tmp = tmp.left; oldTmp.left = tmp.right; tmp.right = oldTmp; grand.right = tmp; } // If left dont exists // add 1 to count and // traverse further right to // flatten remaining BST. else { count++; grand = tmp; tmp = tmp.right; } } return count; } // Function to compress given tree // with its root as grand.right. static void compress(TreeNode grand, int m) { // Make tmp pointer to traverse // and compress the given BST. TreeNode tmp = grand.right; // Traverse and left-rotate root m times // to compress given vine form of BST. for (int i = 0; i < m; i++) { TreeNode oldTmp = tmp; tmp = tmp.right; grand.right = tmp; oldTmp.right = tmp.left; tmp.left = oldTmp; grand = tmp; tmp = tmp.right; } } // Function to calculate the // log base 2 of an integer static public int log2(int N) { // calculate log2 N indirectly // using log() method int result = (int)(Math.log(N) / Math.log(2)); return result; } // Function to implement the algorithm static TreeNode balanceBST(TreeNode root) { // create dummy node with value 0 TreeNode grand = new TreeNode(0); // assign the right of dummy node as our input BST grand.right = root; // get the number of nodes in input BST and // simultaneously convert it into right linked list. int count = bstToVine(grand); // gets the height of tree in which all levels // are completely filled. int h = log2(count + 1); // get number of nodes until second last level int m = (int)Math.pow(2, h) - 1; // Left rotate for excess nodes at last level compress(grand, count - m); // Left rotation till m becomes 0 // Step is done as mentioned in algo to // make BST balanced. for (m = m / 2; m > 0; m /= 2) { compress(grand, m); } // return the balanced tree return grand.right; } // Function to print preorder traversal // of Binary tree. static void preorderTraversal(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); preorderTraversal(root.left); preorderTraversal(root.right); return; } // Driver code public static void main(String[] args) { TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.left.left = new TreeNode(2); root.left.left.left = new TreeNode(1); // Function call to implement // Day-Stout-Warren algorithm root = balanceBST(root); // To print the preorder traversal of BST preorderTraversal(root); }}// This code is contributed by Lovely Jain |
C#
// C# code to balance BST using DSW algorithmusing System;public class GFG { // Defining the structure for TreeNode. class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; left = right = null; } } // Function to convert input BST // to right linked list // known as vine or backbone. static int bstToVine(TreeNode grand) { int count = 0; // Make tmp pointer to traverse // and right flatten the given BST. TreeNode tmp = grand.right; // Traverse until tmp becomes NULL while (tmp != null) { // If left exist for node // pointed by tmp then // right rotate it. if (tmp.left != null) { TreeNode oldTmp = tmp; tmp = tmp.left; oldTmp.left = tmp.right; tmp.right = oldTmp; grand.right = tmp; } // If left dont exists // add 1 to count and // traverse further right to // flatten remaining BST. else { count++; grand = tmp; tmp = tmp.right; } } return count; } // Function to compress given tree // with its root as grand.right. static void compress(TreeNode grand, int m) { // Make tmp pointer to traverse // and compress the given BST. TreeNode tmp = grand.right; // Traverse and left-rotate root m times // to compress given vine form of BST. for (int i = 0; i < m; i++) { TreeNode oldTmp = tmp; tmp = tmp.right; grand.right = tmp; oldTmp.right = tmp.left; tmp.left = oldTmp; grand = tmp; tmp = tmp.right; } } // Function to calculate the // log base 2 of an integer static public int log2(int N) { // calculate log2 N indirectly // using log() method int result = (int)(Math.Log(N) / Math.Log(2)); return result; } // Function to implement the algorithm static TreeNode balanceBST(TreeNode root) { // create dummy node with value 0 TreeNode grand = new TreeNode(0); // assign the right of dummy node as our input BST grand.right = root; // get the number of nodes in input BST and // simultaneously convert it into right linked list. int count = bstToVine(grand); // gets the height of tree in which all levels // are completely filled. int h = log2(count + 1); // get number of nodes until second last level int m = (int)Math.Pow(2, h) - 1; // Left rotate for excess nodes at last level compress(grand, count - m); // Left rotation till m becomes 0 // Step is done as mentioned in algo to // make BST balanced. for (m = m / 2; m > 0; m /= 2) { compress(grand, m); } // return the balanced tree return grand.right; } // Function to print preorder traversal // of Binary tree. static void preorderTraversal(TreeNode root) { if (root == null) return; Console.Write(root.val + " "); preorderTraversal(root.left); preorderTraversal(root.right); return; } static public void Main() { // Code TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.left.left = new TreeNode(2); root.left.left.left = new TreeNode(1); // Function call to implement // Day-Stout-Warren algorithm root = balanceBST(root); // To print the preorder traversal of BST preorderTraversal(root); }}// This code is contributed by lokesh(lokeshmvs21). |
Javascript
<script>// Javascript code to balance BST using DSW algorithm.// Defining the structure for TreeNode.class TreeNode { constructor(x = 0, left = null, right = null){ this.val = x this.left = left this.right = right }}// Function to convert input BST // to right linked list// known as vine or backbone.function bstToVine(grand) { let count = 0; // Make tmp pointer to traverse // and right flatten the given BST. let tmp = grand.right; // Traverse until tmp becomes NULL while (tmp) { // If left exist for node // pointed by tmp then // right rotate it. if (tmp.left) { let oldTmp = tmp; tmp = tmp.left; oldTmp.left = tmp.right; tmp.right = oldTmp; grand.right = tmp; } // If left dont exists // add 1 to count and // traverse further right to // flatten remaining BST. else { count++; grand = tmp; tmp = tmp.right; } } return count;}// Function to compress given tree// with its root as grand.right.function compress(grand, m) { // Make tmp pointer to traverse // and compress the given BST. let tmp = grand.right; // Traverse and left-rotate root m times // to compress given vine form of BST. for (let i = 0; i < m; i++) { let oldTmp = tmp; tmp = tmp.right; grand.right = tmp; oldTmp.right = tmp.left; tmp.left = oldTmp; grand = tmp; tmp = tmp.right; }}// Function to implement the algorithmfunction balanceBST(root) { // create dummy node with value 0 let grand = new TreeNode(0); // assign the right of dummy node as our input BST grand.right = root; // get the number of nodes in input BST and // simultaneously convert it into right linked list. let count = bstToVine(grand); // gets the height of tree in which all levels // are completely filled. let h = Math.log2(count + 1); // get number of nodes until second last level let m = Math.pow(2, h) - 1; // Left rotate for excess nodes at last level compress(grand, count - m); // Left rotation till m becomes 0 // Step is done as mentioned in algo to // make BST balanced. for (m = Math.floor(m / 2); m > 0; m = Math.floor(m / 2)) { compress(grand, m); } // return the balanced tree return grand.right;}// Function to print preorder traversal// of Binary tree.function preorderTraversal(root) { if (!root) return; document.write(root.val + " "); preorderTraversal(root.left); preorderTraversal(root.right); return;}// Driver codelet root = new TreeNode(10);root.left = new TreeNode(5);root.left.left = new TreeNode(2);root.left.left.left = new TreeNode(1);// Function call to implement // Day-Stout-Warren algorithmroot = balanceBST(root);// To print the preorder traversal of BSTpreorderTraversal(root);// This code is contributed by saurabh_jaiswal.</script> |
Python3
# Python code to balance BST using DSW algorithmimport math# Defining the structure for TreeNodeclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right# Function to convert input BST to right linked list known as vine or backbone.def bstToVine(grand: TreeNode) -> int: count = 0 # Make tmp pointer to traverse and right flatten the given BST tmp = grand.right # while tmp is not null while tmp: # If left exist for node pointed by tmp then right rotate it if tmp.left: oldTmp = tmp tmp = tmp.left oldTmp.left = tmp.right tmp.right = oldTmp grand.right = tmp # If left dont exists add 1 to count and traverse further right to flatten remaining BST else: count += 1 grand = tmp tmp = tmp.right return count# Function to compress given tree with its root as grand.rightdef compress(grand: TreeNode, m: int) -> None: # Make tmp pointer to traverse and compress the given BST tmp = grand.right # Traverse and left-rotate root m times to compress given vine form of BST for i in range(m): oldTmp = tmp tmp = tmp.right grand.right = tmp oldTmp.right = tmp.left tmp.left = oldTmp grand = tmp tmp = tmp.right# Function to implement the algorithmdef balanceBST(root: TreeNode) -> TreeNode: # create dummy node with value 0 grand = TreeNode(0) # assign the right of dummy node as our input BST grand.right = root # get the number of nodes in input BST and simultaneously convert it into right linked list. count = bstToVine(grand) # get the height of tree in which all levels are completely filled h = int(math.log2(count + 1)) # get number of nodes until second last level m = pow(2, h) - 1 # left rotate for excess nodes at last level compress(grand, count - m) # left rotate till m becomes 0 # Steps is done as mentioned in algorithm to make BST balanced. for m in [m // 2**i for i in range(1, h + 1)]: compress(grand, m) # return the root of the balanced binary search tree return grand.right# Function to print preorder traversal of Binary treedef preorderTraversal(root: TreeNode) -> None: if not root: return print(root.val, end=" ") preorderTraversal(root.left) preorderTraversal(root.right) return# Driver codeif __name__ == "__main__": root = TreeNode(10) root.left = TreeNode(5) root.left.left = TreeNode(2) root.left.left.left = TreeNode(1) # Function call to implement Day-Stout-Warren algorithm root = balanceBST(root) # To print the preorder traversal of BST preorderTraversal(root) |
Output
5 2 1 10
Time Complexity: O(N) where N is the total number of nodes in the BST
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
