BST from Preorder Traversal 🎯

Welcome to our comprehensive guide on Building a Binary Search Tree (BST) from Preorder Traversal! 📝

In this lesson, we'll learn how to construct a BST from a preorder traversal list. We'll dive deep into understanding the concept, step by step, making it easy for both beginners and intermediates to grasp.

What is Preorder Traversal? 💡

Preorder traversal is a method used to visit every node in a binary tree. In this approach, the root node is visited first, followed by the left subtree, and finally the right subtree.

Why Preorder Traversal for BST Construction? 📝

Preorder traversal is ideal for constructing a BST because it visits the root node first, which holds the data value. This allows us to build the tree by adding nodes in the correct order.

BST from Preorder Traversal Algorithm 💡

Initialize an empty BST.
Iterate through the preorder traversal list.
For each node in the list:
- Create a new node with the current value.
- Insert the new node into the BST based on its value.

Building a BST from Preorder Traversal - Example 🎯

Let's construct a BST from the preorder traversal list: 1 2 4 5 3 6 7.

Here's the code for building the BST:

python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def build_tree(preorder):
    if not preorder:
        return None

    root = Node(preorder[0])
    if len(preorder) > 1:
        # Find the index of the current node's value in the preorder list (excluding the root)
        index = preorder.index(root.data)

        # Split the preorder list into left and right subtrees
        left_preorder = preorder[:index]
        right_preorder = preorder[index+1:]

        # Recursively construct the left and right subtrees
        root.left = build_tree(left_preorder)
        root.right = build_tree(right_preorder)

    return root

# Test the function
preorder = [1, 2, 4, 5, 3, 6, 7]
root = build_tree(preorder)

We hope this guide helps you in understanding how to build a Binary Search Tree from Preorder Traversal. Happy coding! 🎉