Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
This article will teach you to determine if a given array can be a preorder traversal of BST with an optimal solution. First, we will discuss the problem with the brute force method, and after that, we will discuss and implement the optimum solution for this problem.
A binary search tree is a data structure representing the data within a node as a hierarchical structure. Preorder traversal is one of the three traversal methods that we use to iterate over the binary search tree.
Problem Statement
The problem statement here is that we will be given an array of size n, and we need to determine whether this array can represent a preorder traversal of a binary search tree or not.
In preorder, there is a rule that you need to follow for traversal. When doing a preorder traversal, you need to follow this order Root->Left->Right. This means that we will first traverse or visit the current root node and then traverse over the left subtree of the current root node and, after that, the right subtree of the current node.
Keep in mind that in a binary search tree, all elements in the left subtree will be smaller than the current root node, and in the right subtree, all elements will be greater.
Sample Examples
Input: [3,2,1,4]
Output: Given array is a preorder traversal of BST
Explanation
Example 2
Input: [40,30,35,20,80,120]
Output: Given array is not a preorder traversal of BST
Explanation;
If you build the binary search tree of the given array, you will find out that element 20 will be disobeying the right subtree rule. So that is why it cannot be a BST
Brute force Approach
We will just discuss the brute force approach.
Finding the element just larger than the one now to its right will not be the appropriate first step.
Directly verify that every element to its right is greater than the element you have chosen as the current element.
Additionally, every element to the left of the bigger and the user element is now smaller than it.
Recursively check the same condition from the current element to an element smaller than the just bigger element for the left subarray.
Additionally, recursively look for a subarray that contains just a single bigger element.
This method is ineffective since it has an O(N^2) time complexity.
Optimal Approach
We will use the stack for a better approach to improve the time complexity. Using stack, we check if an element in the right subtree is smaller than the root node. Then, the given array cannot be a preorder traversal of a binary search tree and will return false. If there is none and it follows the binary search tree conditions, it will return true by default.
For more explanation, check out the above diagram.
Algorithm
Calculate size n of the given array.
Call function isaBST with arguments array and size of the array.
Initialize an empty stack
For loop starts from i=0 till i<n
Check if array[i ] is smaller than the root node returns false if it is true.
Intialize while loop with condition stackisnotempty and stacktop < array[ i ].
If while loop is true:
rootnode = stacktop;
stack.pop();
End while if false
Push element in the stack.
End for loop
Return true.
Print the result
End
Implementation
C++
#include<bits/stdc++.h>
using namespace std;
bool isaBST(int givenarray[], int n) {
/*Initialize an empty stack */
stack < int > bst;
int rootnode = INT_MIN;
/* Iterate over given array */
for (int i = 0; i < n; i++) {
/* If we find an element in right subtree smaller than root node we will return false*/
if (givenarray[i] < rootnode)
return false;
/* Reason for this while loop is to check whether the current element is not disobeying the right subtree rule*/
while (!bst.empty() && bst.top() < givenarray[i]) {
rootnode = bst.top();
bst.pop();
}
/* Pushing in stack */
bst.push(givenarray[i]);
}
return true;
}
/* Driver program */
int main() {
int givenarray[] = { 3, 2, 1, 4 };
int n = sizeof(givenarray) / sizeof(givenarray[0]);
if (!isaBST) {
cout << "Given array is a preorder traversal of BST" << endl;
}
cout << "Given array is not a preorder traversal of BST" << endl;
return 0;
}
You can also try this code with Online C++ Compiler
INT_MIN = -2**32
def isaBST(givenarray ):
# Initialize an empty stack
bst = []
rootnode = INT_MIN
# Iterate over the given array
for value in givenarray :
if value < rootnode :
return False
# Reason for this while loop is to check whether the current element is not disobeying the right subtree rule
while(len(bst) > 0 and bst[-1] < value) :
rootnode = bst.pop()
# Pushing in the stack
bst.append(value)
return True
# Main
if __name__ == '__main__':
givenarray = [3,2,1,4]
print ("Given array is a preorder traversal of BST" if isaBST(givenarray) == True else "Given array is not a preorder traversal of BST")
You can also try this code with Online Python Compiler
import java.util.Stack;
class Main {
boolean isaBST(int givenarray[], int n) {
/* Initialize an empty stack */
Stack < Integer > bst = new Stack < Integer > ();
int rootnode = Integer.MIN_VALUE;
/* Iterate over given array */
for (int i = 0; i < n; i++) {
/* If we find an element in right subtree smaller than root node we will return false*/
if (givenarray[i] < rootnode) {
return false;
}
/* Reason for this while loop is to check whether the current element is not disobeying the right subtree rule*/
while (!bst.empty() && bst.peek() < givenarray[i]) {
rootnode = bst.peek();
bst.pop();
}
/* Pushing in stack */
bst.push(givenarray[i]);
}
return true;
}
public static void main(String args[]) {
Main bstobj = new Main();
int[] givenarray = new int[]{ 3, 2, 1, 4 };
int n = givenarray.length;
/* Array result */
if (bstobj.isaBST(givenarray, n) == true) {
System.out.println("Given array is a preorder traversal of BST");
} else {
System.out.println("Given array is not a preorder traversal of BST");
}
}
}
You can also try this code with Online Java Compiler
The time complexity for all the implemented code will be O(n), where n is the size of the given array. We must traverse each element in the array to justify the binary search tree in O(n) complexity.
Space Complexity
Space complexity will be O(n), where n is the size of a given array.
Traversing means visiting nodes on a tree and displaying their data in a particular order.
How many types of traversal are there in the Binary search tree?
There are three types of traversals preorder, inorder and postorder traversal.
All three traversals come under what searching method?
DFS - depth-first search.
Why do we use binary trees?
A binary tree is one of the types of data structures that is mainly used for searching and sorting data. In a binary tree, we store the data hierarchically.
What is the maximum number of nodes a parent node can have in a binary search tree?
In a binary search tree, a node can have a maximum of two nodes as children nodes.
Conclusion
In this article, we learned how to know if a given array is a preorder traversal of a binary search tree with implementation in three different programming languages. Also, we have seen the time complexity for the. We have also discussed the brute force approach, which is not an optimal solution but is better known.
For more Tree data structure articles, you can refer following links: