Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute force Approach
3.
Optimal Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
C++
3.2.2.
PYTHON 
3.2.3.
JAVA
4.
Complexity Analysis
4.1.
Time Complexity
4.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
What does traversing means?
5.2.
How many types of traversal are there in the Binary search tree?
5.3.
All three traversals come under what searching method?
5.4.
Why do we use binary trees?
5.5.
What is the maximum number of nodes a parent node can have in a binary search tree?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find if a given Array can Represent Preorder Traversal of BST

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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

image2
image2

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.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

  1. Calculate size n of the given array.
  2. Call function isaBST with arguments array and size of the array.
  3. Initialize an empty stack
  4. For loop starts from i=0 till i<n
  5. Check if array[i ] is smaller than the root node returns false if it is true.
  6. Intialize while loop with condition stackisnotempty and stacktop < array[ i ].
  7. If while loop is true:
    1.     rootnode = stacktop;
    2.     stack.pop();
  8. End while if false
  9. Push element in the stack.
  10. End for loop
  11. Return true.
  12. Print the result
  13. 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;
}

PYTHON 

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")    

JAVA

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");
    }
  }
}

Input: [3,2,1,4]

Output

output

Complexity Analysis

Time Complexity

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.

You can also read about insertion into bst.

Frequently Asked Questions

What does traversing means?

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:


Check out the following problems - 

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Previous article
Sum and the Product of Minimum and Maximum Elements of a Binary Search Tree
Next article
Find if the given array of size n can represent BST of n levels or not
Live masterclass