Given a sorted list nums of size n, construct a binary search tree by
- Taking nums[k] as the root where k = floor(n / 2).
- Recursively constructing the left subtree using the list nums[:k]
- Recursively constructing the right subtree using the list nums[k + 1:]
Constraints
0 ≤ n ≤ 100,000
Example 1
Input
nums = [0, 1, 2, 3, 4]Output:
2 / \ 1 4 / / 0 3
Recursive Algorithm to Construct Binary Search Tree
The problem itself is recursive and we can build a recursive algorithm. First, find the middle point, build a node, and recursively build its left and right tree. Since the entire list is sorted, the binary tree we build is a Binary Search Tree.
Python algorithm to Build a Binary Search Tree:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildBST(self, nums): if not nums: return None k = len(nums) // 2 root = Tree(nums[k]) root.left = self.buildBST(nums[:k]) root.right = self.buildBST(nums[k+1:]) return root |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildBST(self, nums):
if not nums:
return None
k = len(nums) // 2
root = Tree(nums[k])
root.left = self.buildBST(nums[:k])
root.right = self.buildBST(nums[k+1:])
return rootC++ algorithm to Build a Binary Search Tree:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | /** * class Tree { * public: * int val; * Tree *left; * Tree *right; * }; */ Tree* buildBST(vector<int>& nums) { if (nums.empty()) return nullptr; int k = nums.size() / 2; Tree* root = new Tree(nums[k]); auto left = vector<int>(begin(nums), begin(nums) + k); auto right = vector<int>(begin(nums) + k + 1, end(nums)); root->left = buildBST(left); root->right = buildBST(right); return root; } |
/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
Tree* buildBST(vector<int>& nums) {
if (nums.empty()) return nullptr;
int k = nums.size() / 2;
Tree* root = new Tree(nums[k]);
auto left = vector<int>(begin(nums), begin(nums) + k);
auto right = vector<int>(begin(nums) + k + 1, end(nums));
root->left = buildBST(left);
root->right = buildBST(right);
return root;
}Both implementations are O(N^2) time where N is the number of the values in the list because at each partition, we are allocating spaces and copying over the sublists. There is O(N) space where we are implicitly requiring a stack because of using stack.
If we are using the left, right pointer to avoid the sublist copying, the time complexity will be O(N):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | /** * class Tree { * public: * int val; * Tree *left; * Tree *right; * }; */ Tree* buildBST(vector<int>& nums) { if (nums.empty()) return nullptr; function<Tree*(vector<int>&, int, int)> build = [&](vector<int>& nums, int left, int right) { if (left > right) return (Tree*)NULL; int k = (left + right + 1) >> 1; Tree* root = new Tree(nums[k]); root->left = build(nums, left, k - 1); root->right = build(nums, k + 1, right); return root; }; return build(nums, 0, nums.size() - 1); } |
/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
Tree* buildBST(vector<int>& nums) {
if (nums.empty()) return nullptr;
function<Tree*(vector<int>&, int, int)> build = [&](vector<int>& nums, int left, int right) {
if (left > right) return (Tree*)NULL;
int k = (left + right + 1) >> 1;
Tree* root = new Tree(nums[k]);
root->left = build(nums, left, k - 1);
root->right = build(nums, k + 1, right);
return root;
};
return build(nums, 0, nums.size() - 1);
}–EOF (The Ultimate Computing & Technology Blog)
loading...
Last Post: Compute the Z Sum of a Matrix
Next Post: Teaching Kids Programming - Hexadecimal Numbers Conversion
