{"id":4280,"date":"2021-11-25T19:30:00","date_gmt":"2021-11-25T14:00:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4280"},"modified":"2021-11-25T17:36:23","modified_gmt":"2021-11-25T12:06:23","slug":"sorted-array-to-balanced-bst","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/sorted-array-to-balanced-bst\/","title":{"rendered":"Sorted Array to Balanced BST"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#approach-recursive-solution\">Approach: Recursive Solution<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given an array <strong>A[] <\/strong>of size <strong>N<\/strong>, sorted in ascending order. The task is to convert it into balanced <strong>BST<\/strong>.<br>A balanced BST is a binary tree in which the height of the left subtree and right subtree is not more than <strong>one.<\/strong><\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"550\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"input and output\"  class=\"wp-image-4422 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-and-output-1024x550.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-and-output-1024x550.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-and-output-300x161.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-and-output-768x412.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-and-output-380x204.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-and-output-550x295.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-and-output-800x429.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-and-output-1160x623.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-and-output.png 1211w\" ><\/figure>\n\n\n\n<h2 id=\"approach-recursive-solution\">Approach: Recursive Solution<\/h2>\n\n\n\n<p>Since the array is <strong>sorted, <\/strong>taking advantage of this fact, the idea is to build the tree by dividing the array into <strong>two parts<\/strong>.<br>Let us consider the index as <strong>mid<\/strong>, where the array has been divided.<\/p>\n\n\n\n<p>Since in a binary search tree, the elements to the left of a node are smaller and elements to the right are greater. Similarly, to construct the tree, the element to the left of mid would consist of the left subtree and elements to its right would consist of the right subtree. This can be solved recursively till no more elements would be left.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"550\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"pick element\"  class=\"wp-image-4423 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/pick-element-1024x550.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/pick-element-1024x550.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/pick-element-300x161.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/pick-element-768x412.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/pick-element-380x204.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/pick-element-550x295.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/pick-element-800x429.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/pick-element-1160x623.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/pick-element.png 1211w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Consider the element at the middle of the array and make it the root of the tree.<\/li><li>Now make a recursive function and for each half:<ul><li>Find the middle element of the left half and make it the root of the left child.<\/li><li>Find the middle element of the right half and make it the root of the right child.<\/li><\/ul><\/li><li>Continue recursing for each half until all elements have been inserted in the tree.<\/li><\/ul>\n\n\n\n<p id=\"-implementation-of-the-approach-\"><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">TreeNode * sortedArrayToBST(vector &amp;lt; int > &amp;amp; nums) {\n  int len = nums.size();\n  TreeNode * root = NULL;\n  return helper(root, nums, 0, len - 1);\n}\n \nTreeNode * helper(TreeNode * root, vector &amp;lt; int > &amp;amp; nums, int l, int r) {\n  if (l &amp;lt;= r) {\n    int m = l + (r - l) \/ 2;\n    root = new TreeNode(nums[m]);\n    root -> left = helper(NULL, nums, l, m - 1);\n    root -> right = helper(NULL, nums, m + 1, r);\n  }\n  return root;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public TreeNode helper(int left, int right) {\n  if (left > right) return null;\n  int p = (left + right) \/ 2;\n  TreeNode root = new TreeNode(nums[p]);\n  root.left = helper(left, p - 1);\n  root.right = helper(p + 1, right);\n  return root;\n}\n \npublic TreeNode sortedArrayToBST(int[] nums) {\n  return helper(0, nums.length - 1);\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def sortedArrayToBST(nums):\n    def helper(left, right):\n        if left > right:\n            return None\n \n        p = (left + right) \/\/ 2\n        root = TreeNode(nums[p])\n        root.left = helper(left, p - 1)\n        root.right = helper(p + 1, right)\n        return root\n \n    return helper(0, len(nums) - 1)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N), where N\u00a0 is the total size of the array.<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(h), where h is the height of the tree.<\/p>\n\n\n\n<p id=\"-practice-questions-\"><strong>Practice Questions:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/sorted-array-to-balanced-bst\/\" target=\"_blank\" rel=\"noreferrer noopener\">Sorted Array To Balanced BST<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ul><li><strong>What is the time and space complexity of the recursive approach?<\/strong><strong><br><\/strong>The time and space complexity of the recursive approach is O(N) and O(h).<\/li><\/ul>\n\n\n\n<ul><li><strong>&nbsp;What is a Binary Search Tree?<br><\/strong>A <strong>Binary Search Tree <\/strong>is a binary tree that satisfies the following property:<ol><li>The left node value is smaller than its parents.<\/li><li>The right node value is greater than its parents.<\/li><\/ol><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Given an array A[] of size N, sorted in ascending order. The task is to convert it into&hellip;\n","protected":false},"author":5,"featured_media":4424,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[608],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4280"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4280"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4280\/revisions"}],"predecessor-version":[{"id":4425,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4280\/revisions\/4425"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4424"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4280"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}