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 nonleaf 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.

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

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

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

Reverse InOrder:
 Traverse the right subtree by recursively calling the reverse inorder 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 inorder function for the root of left subtree.
 For the BST shown in the above figure, reverse inorder: 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 subtree
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 subtree
else:
if (node.right == None):
node.right = new_node
break
else:
node = node.right
return root
Evaluation:
Recent Posts
Archive
Tags