Given an integer array nums sorted in ascending order, convert it into a height-balanced Binary Search Tree and return the root of the tree.
A height-balanced BST means that for every node, the height difference between its left subtree and right subtree is at most 1.
Example 1
Input: nums = [-10, -3, 0, 5, 9]
Output: [0, -10, 5, null, -3, null, 9]
Explanation: The middle element 0 becomes the root. Values smaller than 0 go to the left subtree, and values greater than 0 go to the right subtree.
Example 2
Input: nums = [1, 3]
Output: [1, null, 3]
Explanation: For an even-sized range, choosing either middle value can still give a valid balanced BST. Here, 1 is chosen as root and 3 becomes its right child.
Approach
The sorted array already tells the BST order.
If an element is chosen as the root, every element before it in the array is smaller, so those elements belong to the left subtree. Every element after it is larger, so those elements belong to the right subtree.
To keep the tree balanced, the root should not be too close to the start or the end of the current range. The best choice is the middle element, because it leaves almost the same number of elements on both sides.
Then the same idea is repeated for the left half and the right half. Each recursive call builds one balanced subtree.
Algorithm
Start with the full array range from index
0ton - 1. This range represents the part of the array that must become the current subtree.If the current range is empty, return
null. This is needed because there are no values left to create a node.Find the middle index of the current range. The middle value becomes the root so that both sides get almost equal numbers of nodes.
Recursively build the left subtree from the values before the middle index. These values are smaller than the root, so they belong on the left.
Recursively build the right subtree from the values after the middle index. These values are larger than the root, so they belong on the right.
Return the created root node so it can be attached to its parent subtree.
Dry Run
Convert Sorted Array into BST
Solution
#include <bits/stdc++.h>using namespace std;struct TreeNode { int val; TreeNode* left; TreeNode* right; // Creates a tree node with no children at first. TreeNode(int value) { val = value; left = nullptr; right = nullptr; }};class Solution {private: // Builds a balanced BST from nums[left] to nums[right]. TreeNode* buildBST(vector<int>& nums, int left, int right) { // If the range is empty, there is no node to create. if (left > right) { return nullptr; } // mid stores the best root position for this subtree. int mid = left + (right - left) / 2; // root stores the middle value as the current subtree root. TreeNode* root = new TreeNode(nums[mid]); // Smaller values before mid form the left subtree. root->left = buildBST(nums, left, mid - 1); // Larger values after mid form the right subtree. root->right = buildBST(nums, mid + 1, right); // Returning root connects this subtree to its parent. return root; } // Prints the preorder traversal of the created BST. void printPreorder(TreeNode* root) { // An empty child contributes nothing to the traversal. if (root == nullptr) { return; } cout << root->val << " "; printPreorder(root->left); printPreorder(root->right); }public: /* Converts a sorted array into a height-balanced BST. The middle value of every range becomes the subtree root. */ TreeNode* sortedArrayToBST(vector<int>& nums) { return buildBST(nums, 0, nums.size() - 1); } // Prints the preorder traversal of the created BST. void printTree(TreeNode* root) { printPreorder(root); }};// Driver code startsint main() { vector<int> nums = {-10, -3, 0, 5, 9}; Solution solution; // root stores the final balanced BST. TreeNode* root = solution.sortedArrayToBST(nums); cout << "Preorder traversal: "; solution.printTree(root); return 0;}Complexity Analysis
Time Complexity: O(N), N is the size of array, because every array element is used exactly once to create one tree node.
Space Complexity: O(log N) , N is the size of array, auxiliary space for the recursion stack because the constructed tree is height-balanced. The output tree itself uses O(N) space.
Interview follow-up Questions
The middle element gives almost equal numbers of nodes to the left and right subtrees. This helps keep the tree height-balanced.
Be the first to add a comment.