Recursive Algorithm to Convert a List to Binary Search Tree

ACMer

4 years ago

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:

# 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 root

C++ algorithm to Build a Binary Search Tree:

/**
 * 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):

/**
 * 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)

526 words
Last Post: Compute the Z Sum of a Matrix
Next Post: Teaching Kids Programming - Hexadecimal Numbers Conversion

The Permanent URL is: Recursive Algorithm to Convert a List to Binary Search Tree (AMP Version)

Recursive Algorithm to Construct Binary Search Tree

Related posts: