Convert Sorted List to Binary Search Tree (BST)

Welcome to this comprehensive guide on converting a sorted list into a Binary Search Tree (BST)! In this lesson, we'll learn about the concept of BST, why it's important, and how to convert a sorted list into a BST.

By the end of this lesson, you'll be able to:

Understand the Binary Search Tree (BST) data structure
Learn how a sorted list can be used to create a BST
Write code to convert a sorted list into a BST in Python

What is a Binary Search Tree (BST)? 🎯

A Binary Search Tree (BST) is a tree data structure where each node has at most two children, referred to as the left child and the right child. The left child has a value less than the parent node, while the right child has a value greater than the parent node. This property allows for efficient search, insertion, and deletion operations.

Why convert a sorted list to a BST? 📝

Converting a sorted list to a BST is a common operation in computer science. It's useful for problems that require a balanced binary tree, where the depth of the left and right subtrees differs by at most one. This process helps us build a BST quickly and efficiently from a sorted list.

Converting a Sorted List to a BST 💡

To convert a sorted list to a BST, we start by selecting the middle element of the list as the root node. Then, we recursively build the left and right subtrees by taking the elements less than the root for the left subtree and the elements greater than the root for the right subtree.

Here's a step-by-step example:

Let's take a sorted list: [4, 2, 6, 1, 3, 7]
The middle element is 4. We make it the root node.

python

root = 4
left = []
right = []

Split the list into two: [2, 1, 3] (left) and [6, 7] (right)
Recursively build the left subtree by taking the elements less than 4:

python

def build_left(arr, node):
    if not arr:
        return None

    middle = len(arr) // 2
    left_node = arr[middle]
    arr_left = arr[:middle]
    arr_right = arr[middle + 1:]

    left = build_left(arr_left, left_node)

    return {
        "value": left_node,
        "left": left,
        "right": build_right(arr_right, node)
    }

Recursively build the right subtree by taking the elements greater than 4:

python

def build_right(arr, node):
    if not arr:
        return None

    middle = len(arr) // 2
    right_node = arr[middle]
    arr_left = arr[:middle]
    arr_right = arr[middle + 1:]

    right = build_right(arr_right, right_node)

    return {
        "value": right_node,
        "left": build_left(arr_left, node),
        "right": right
    }

Finally, assign the left and right subtrees to our root node:

python

root = build_left([2, 1, 3], root)
root = build_right([6, 7], root)

Now, our BST is complete! You can verify the structure by printing the values in the BST or traversing the tree.

Practice Time 💡

Now that you've learned about converting a sorted list to a BST, let's put your knowledge to the test with a quiz:

Keep learning and practicing! Happy coding! 🚀🚀🚀