Build the binary search tree from a preorder sequence

The Binary Trees are fundamentally one of the most efficient data structures that provides their own methods of traversal for a problem set.

What's fun about the Binary Trees is that you can basically use the four different traversal methods such as in-order, level order, preorder and post order traversals for navigating through the structure for finding the right solution.

This essentially means that on a surface level, one is not required to find other algorithms and approaches for solving Binary Tree problems.

One such algorithm is the preorder traversal method that is the topic of discussion of the blog! 

Did you know by revoking the BST in preorder algorithm, you can construct the binary search tree within a program?

Which is why, the intent of this blog is to provide more detailed information for Preorder Traversal in the BST and the algorithms related to this approach.

What do you mean by Pre-Order Traversal in a Binary Tree?

Did you know that there are essentially four different types of traversal methods that are used for solving any given Binary Tree problem?

Namely they are:

• In-Order Traversal

In this approach the left part of the Binary Tree is visited first, following the root and lastly the right part of the BST.

• Pre-Order Traversal

For finding BST in preorder, we visit the root of the tree first, followed by the left subtree and finally the right.

• Post-Order Traversal 

This method works completely opposite to the pre-order traversal since here, we essentially visit the root of the Binary Tree lastly. We will begin with the left subtree, move to the right and finally visit the root of the tree.

• Level Order Traversal

For this approach we traverse the given tree structure in a leveled order. Meaning, that the first level of the Binary Tree will be visited first, following the other levels and finally by continuing this process, we will reach the last level of nodes.

Now, that was a beginner level refresher for traversing a BST or the binary search tree. 

Let us get into detail what BST in preorder actually entails.

What is BST in Preorder? 

Essentially, a preorder traversal within a Binary Tree as briefly mentioned above is the approach where the root of the tree is visited first, followed by the left part of the BST i.e left subtree and finally we reach the right part of the BST of the given BST.

The Binary Tree Traversal that is related to Pre-Order Traversal performs a Depth First Search. The algorithm for this method ensures that all the nodes of the tree have been effectively traversed as we move in an ascending order of nodes.

BST in Preorder certainly helps in maintaining a uniformity in the travel order of nodes thus removing the need to perform a recursive function by the end of the program.

Once all the nodes have been visited, the programmer can simply check for the required output and print the results as either true or false by the end of the program.

Now, we have provided enough details about preorder traversal in the binary search tree. In the following section, find the process of implementation for the Pre-Order Traversal Approach.

How to build a BST using the given Pre-Order Sequence?

Read the following problem statement and we will describe how you can find out BST from preorder using different approaches and algorithms.

Problem Statement:

You have been provided a preorder traversal of a BST i.e the binary search tree. Your task is to construct a BST using this data.

Now, moving onto the methods, the following approaches have the highest accuracy and affect the least amount of time complexity.

Method 1: Implementing the Naive Approach

Since we are using the preorder traversal method, naturally, we will begin by constructing the root of the BST. 

Here's how the algorithm for the Naive Approach would work:

• Start by constructing the root.

• Afterwards, we will move onto the defining the first element whose value will be greater as compared to the root. Let us name this index as "i".

• Now, the values that will be inserted between the root node and the index "i" will form the left part of the BST.

• Also, the values between the index "i" and the "n-i" index will form the right part of the BST i.e the right part of the BST.

• Finally, we will recur the values from the "i" index to separate the left subtree from the right.

Time Complexity for this approach:

O(N2)

Method 2: Using the concept of Recursion

The idea for using the recursive algorithm is to create new nodes for the BST and implement them finally by the end of the program. You can also find the nth prime number value contained in a BST using the recursive approach. 

Follow the algorithm mentioned below for creating BST from preorder using the Recursive Algorithm:

•  Start by creating a new node for all the values of the given array.

• Now, the next step is to create the binary search tree by making use of these nodes and inserting them in the right positions following the rules of the BST as mentioned in Data Structures and Algorithms.

• Finally, once all the values of the nodes have been implemented, you can go ahead and print the inorder for the Binary Search Tree.

Time Complexity for this approach:

O(N*log N)

Method 3: Setting a range for every node of the BST

Check out how setting a range for every node of the tree would work:

• You can start by initialising the range as {INT_MIN.. INT_MAX}

• Next up, create the root node within a range.

• Now, in order to create the left subtree you can use the function {INT_MIN…root->data}

• Similarly, you can create the right part of the BST using the function {root->data…INT_MAX}

Time Complexity for this approach:

O(N)

Winding Up

Did you know that Binary Trees are one of the most commonly asked questions in the coding interviews?

From the concepts of BST to finding the nth prime number on a given Binary Tree Data, the Binary Tree coding questions are extremely pivotal for the coding interviews especially for candidates who aspire to be stack developers or a Software Engineer.