April 22, 2020 ### 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)

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

Recent Posts
Categories
Archive
Tags