{"id":2601,"date":"2024-03-17T13:00:00","date_gmt":"2024-03-17T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2601"},"modified":"2024-03-21T08:00:11","modified_gmt":"2024-03-21T08:00:11","slug":"balance-binary-search-tree","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/balance-binary-search-tree\/","title":{"rendered":"Balance A Binary Search Tree ( C++, Java, Python)"},"content":{"rendered":"\n

Binary Search Tree is the most important topic from the interview perspective. It helps you to find the value in the tree in Log(n) time complexity, unlike the normal tree. In this article, we will try the leetcode problem on how to Balance a Binary Search Tree.<\/p>\n\n\n\n

Balance a Binary Search Tree problem<\/strong><\/h2>\n\n\n\n

In the Balance BST problem, we have given a binary search tree. We have to create another binary search tree that is a balanced version of the given tree. A balanced BST is a BST in which the absolute difference between the left height – right height\u00a0 <= 1. There may be more than one answer you can return any of them.\u00a0<\/strong><\/p>\n\n\n\n

Let\u2019s understand this with an example:<\/p>\n\n\n\n

\"Given<\/figure>\n\n\n\n

Left and right height of the root node.<\/p>\n\n\n\n

\"Left<\/figure>\n\n\n\n

The Balanced BST of the given tree looks like<\/p>\n\n\n\n

\"Balanced<\/figure>\n\n\n\n

An In-order Traversal Approach<\/strong><\/h2>\n\n\n\n

In this approach, we will find the in-order traversal<\/a> of the given BST. After finding the inorder traversal we will create a function that takes the middle element of the inorder traversal and inorder array. <\/p>\n\n\n\n

After that, we will call the left side of the middle value to create the left subtree and the right side of the middle value to create the right subtree.<\/p>\n\n\n\n

Let\u2019s examine the approach step by step:<\/p>\n\n\n\n

    \n
  1. First, create a vector or an array that will store the in-order traversal of the given BST.<\/li>\n\n\n\n
  2. Now create a function name inorder_traversal. Pass the root and the vector into that function.<\/li>\n\n\n\n
  3. Call the same function for the left subtree. Then store the value of the current node in the vector. And call the function for the right subtree.<\/li>\n\n\n\n
  4. Once we get the inorder traversal call the BST function. Pass the vector generated through the in-order function. Pass starting index i.e. 0 and ending index i.e. size of the array.<\/li>\n\n\n\n
  5. Find the middle of the starting and ending index. Call the BST function, passing the left part of the middle value to get the left subtree. Call the BST function, passing the right part of the middle value to get the right subtree.<\/li>\n<\/ol>\n\n\n\n

    The below example shows the inorder traversal of the BST.<\/p>\n\n\n\n

    \"In-order<\/figure>\n\n\n\n

    Let\u2019s examine the code for the above process.<\/p>\n\n\n\n

    C++ Code<\/strong><\/h3>\n\n\n\n

    Here is the C++ program to balance a binary search tree:<\/p>\n\n\n\n

    #include<bits\/stdc++.h>\n\nusing namespace std;\n\n\u00a0\u00a0\u00a0\u00a0class TreeNode{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0public:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int data;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0TreeNode* left;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0TreeNode* right;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0TreeNode(int x){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0data = x;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0left = NULL;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0right = NULL;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0};\n\n\u00a0\u00a0\u00a0\u00a0void inorder_traversal(TreeNode* root, vector<TreeNode*>& v){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(root == NULL) return;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0inorder_traversal(root->left, v);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0v.push_back(root);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0inorder_traversal(root->right, v);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0TreeNode* BST(int start, int end, vector<TreeNode*>& v) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (start > end) return NULL;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int mid = (start + end) \/ 2;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0TreeNode* root = v[mid];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root->left = BST(start, mid - 1, v);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root->right = BST(mid + 1, end, v);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return root;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0void print_BST(TreeNode* root){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(root == NULL) return;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0print_BST(root->left);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0cout<<root->data<<" ";\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0print_BST(root->right);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0int main(){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0TreeNode* root = new TreeNode(5);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root->left = new TreeNode(4);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root->left->left = new TreeNode(3);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root->left->left->left = new TreeNode(2);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root->left->left->left->left = new TreeNode(1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0vector<TreeNode*>v;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0inorder_traversal(root, v);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int n = v.size();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0TreeNode* new_root = BST(0, n-1, v);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ in-order traverse of balanced BST\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0cout<<"inorder traversal of new BST is ";\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0print_BST(new_root);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return 0;\n\n\u00a0\u00a0\u00a0\u00a0}<\/pre><\/div>\n\n\n\n
    Java Code<\/strong><\/h3>\n\n\n\n
    Here is the Java program to balance a binary search tree:<\/p>\n\n\n\n
    import java.util.*;\n\nclass TreeNode {\n    int data;\n    TreeNode left, right;\n\n    TreeNode(int x) {\n        data = x;\n        left = null;\n        right = null;\n    }\n}\n\npublic class Main {\n    static void inorderTraversal(TreeNode root, ArrayList<TreeNode> v) {\n        if (root == null)\n            return;\n        inorderTraversal(root.left, v);\n        v.add(root);\n        inorderTraversal(root.right, v);\n    }\n\n    static TreeNode BST(int start, int end, ArrayList<TreeNode> v) {\n        if (start > end)\n            return null;\n        int mid = (start + end) \/ 2;\n        TreeNode root = v.get(mid);\n        root.left = BST(start, mid - 1, v);\n        root.right = BST(mid + 1, end, v);\n        return root;\n    }\n\n    static void printBST(TreeNode root) {\n        if (root == null)\n            return;\n        printBST(root.left);\n        System.out.print(root.data + " ");\n        printBST(root.right);\n    }\n\n    public static void main(String[] args) {\n        TreeNode root = new TreeNode(5);\n        root.left = new TreeNode(4);\n        root.left.left = new TreeNode(3);\n        root.left.left.left = new TreeNode(2);\n        root.left.left.left.left = new TreeNode(1);\n\n        ArrayList<TreeNode> v = new ArrayList<>();\n        inorderTraversal(root, v);\n        int n = v.size();\n        TreeNode newRoot = BST(0, n - 1, v);\n\n        \/\/ Inorder traversal of balanced BST\n        System.out.print("Inorder traversal of new BST is ");\n        printBST(newRoot);\n    }\n}\n<\/pre><\/div>\n\n\n\n
    Python Code<\/strong><\/h3>\n\n\n\n
    We can implement it in Python also:<\/p>\n\n\n\n
    class TreeNode:\n\n\u00a0\u00a0\u00a0\u00a0def __init__(self, x):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0self.data = x\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0self.left = None\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0self.right = None\n\ndef inorder_traversal(root, v):\n\n\u00a0\u00a0\u00a0\u00a0if root is None:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return\n\n\u00a0\u00a0\u00a0\u00a0inorder_traversal(root.left, v)\n\n\u00a0\u00a0\u00a0\u00a0v.append(root)\n\n\u00a0\u00a0\u00a0\u00a0inorder_traversal(root.right, v)\n\ndef BST(start, end, v):\n\n\u00a0\u00a0\u00a0\u00a0if start > end:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return None\n\n\u00a0\u00a0\u00a0\u00a0mid = (start + end) \/\/ 2\n\n\u00a0\u00a0\u00a0\u00a0root = v[mid]\n\n\u00a0\u00a0\u00a0\u00a0root.left = BST(start, mid - 1, v)\n\n\u00a0\u00a0\u00a0\u00a0root.right = BST(mid + 1, end, v)\n\n\u00a0\u00a0\u00a0\u00a0return root\n\ndef print_BST(root):\n\n\u00a0\u00a0\u00a0\u00a0if root is None:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return\n\n\u00a0\u00a0\u00a0\u00a0print_BST(root.left)\n\n\u00a0\u00a0\u00a0\u00a0print(root.data, end=" ")\n\n\u00a0\u00a0\u00a0\u00a0print_BST(root.right)\n\nif __name__ == "__main__":\n\n\u00a0\u00a0\u00a0\u00a0root = TreeNode(5)\n\n\u00a0\u00a0\u00a0\u00a0root.left = TreeNode(4)\n\n\u00a0\u00a0\u00a0\u00a0root.left.left = TreeNode(3)\n\n\u00a0\u00a0\u00a0\u00a0root.left.left.left = TreeNode(2)\n\n\u00a0\u00a0\u00a0\u00a0root.left.left.left.left = TreeNode(1)\n\n\u00a0\u00a0\u00a0\u00a0v = []\n\n\u00a0\u00a0\u00a0\u00a0inorder_traversal(root, v)\n\n\u00a0\u00a0\u00a0\u00a0n = len(v)\n\n\u00a0\u00a0\u00a0\u00a0new_root = BST(0, n - 1, v)\n\n\u00a0\u00a0\u00a0\u00a0# In inorder to traverse of balanced BST\n\n\u00a0\u00a0\u00a0\u00a0print("inorder traversal of new BST is ", end="")\n\n\u00a0\u00a0\u00a0\u00a0print_BST(new_root)<\/pre><\/div>\n\n\n\n
    Output<\/strong>: <\/p>\n\n\n\n
    inorder traversal of new BST is 1 2 3 4 5 <\/code><\/pre>\n\n\n\n
    The time complexity to balance a binary search tree using in-order traversal is O(n), Where n is the total number of nodes present in the given BST. As we are calling two functions one is inorder_traversal and another is BST both time complexity is O(n).<\/p>\n\n\n\n
    The space complexity is also O(n). We are storing the values of nodes in the array.<\/p>\n\n\n\n
    Conclusion<\/strong><\/h2>\n\n\n\n
    In this article, we solved the Blaance Binary Search Tree problem from leetcode<\/a>. Remember that if BST is not balanced then the searching operation may take O(n) time. But by balancing the BST time and complexity will reduced to O(log(n)). <\/p>\n","protected":false},"excerpt":{"rendered":"
    We will solve the leetcode problem to Balance a Binary Search Tree using in-order traversal approach and implement it in C++, Java, and Python.<\/p>\n","protected":false},"author":14,"featured_media":2615,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-2601","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2601","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2601"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2601\/revisions"}],"predecessor-version":[{"id":2754,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2601\/revisions\/2754"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2615"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2601"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2601"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2601"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}