April 22, 2020
LeetCode 1008: Construct Binary Search Tree from Preorder Traversal

Description:

Return the root node of a binary search tree (BST) that matches the given preorder traversal.

Binary Search Tree (BST):

BSTs are tree based ordered data sctructures. As name suggests, every non-leaf node has only two (Binary) children. Every left child is less than the parent and every right child is greater than the parent. By this they enable some operations like lookup to utilise the binary search principle, which significantly reduces the lookup/search time.

In Depth First Search (DFS) of a binary tree, there are four types of tree traversals.

  1. In-Order:

    • Traverse the left subtree first, by recursively calling the in-order function for the root of the left subtree.
    • Read the data part of the current node.
    • Traverse the right subtree by recursively calling the in-order function for the root of the right subtree.
    • For the BST shown in the above figure, in-order: 1, 5, 7, 8, 10, 12
  2. Pre-Order:

    • Read the data part of the current node.
    • Traverse the left subtree by recursively calling the pre-order function for the root of left subtree.
    • Traverse the right subtree by recursively calling the pre-order function for the root of the right subtree.
    • For the BST shown in the above figure, pre-order: 8, 5, 1, 7, 10, 12
  3. Post-Order: 

    • Traverse the left subtree by recursively calling the post-order function for the root of left subtree.
    • Traverse the right subtree by recursively calling the post-order function for the root of the right subtree.
    • Read the data part of the current node.
    • For the BST shown in the above figure, post-order: 1, 7, 5, 12, 10, 8
  4. Reverse In-Order:

    • Traverse the right subtree by recursively calling the reverse in-order function for the root of the right subtree.
    • Read the data part of the current node.
    • Traverse the left subtree by recursively calling the reverse in-order function for the root of left subtree.
    • For the BST shown in the above figure, reverse in-order: 12, 10, 8, 7, 5, 1

Solution:

The following solution is written in Python programming language.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        size = len(preorder)
        # if no elements in preorder then return None
        if (not size):
            return None

        # Initiate the tree with the first element as root
        root = TreeNode(preorder[0])

        for element in preorder[1:]:
            node = root
            new_node = TreeNode(element)
            # Traverse the tree until we find
            # a suitable empty slot for the element
            while (1):
                # if element > node.val go to the left sub-tree
                if (node.val > element):
                    if (node.left == None):
                        node.left = new_node
                        break
                    else:
                        node = node.left

                # if element < node.val go to the right sub-tree
                else:
                    if (node.right == None):
                        node.right = new_node
                        break
                    else:
                        node = node.right

        return root

 

Evaluation:

 

Credits: LeetCode, Wikipedia