Find if the Given Array can represent Level Order Traversal of BST

Introduction

Hi Ninja🥷! In this article, we will learn to solve the problem to find if the given array can represent the Level Order Traversal of BST. We will use the property of BST to solve this problem. I hope you will enjoy and have fun learning a medium-level DSA problem♟ “Find if the given array can represent Level Order Traversal of BST”.

Problem Description🗒️

We have been given an array of size n. We have to find out whether the given array can represent the level order traversal of a BST or not❓

Sample Examples😄

Input: 

Arr[] = {8, 5, 13, 4, 7, 9, 2, 6, 11}

Output: 

Yes

Explanation:

For the given array, Binary Search Tree which can be made is :

Input : 

Arr[] = {550, 250, 140, 550, 150}

Output: 

No

Explanation:

The given array can not represent the level order traversal of a BST:

Approach🤖

The solution to this problem is to store boundaries for each element traversing in level order.

We will store max and min for each node, representing the maximum and minimum values the left and right subtree can have. We will use a queue data structure for level order traversal. 

Every node will store value, max and min, where min represents the lower limit of the left subtree and max represents the upper limit of the right subtree.

The left subtree can have elements ranging from min to the current node value-1. And the elements in the right subtree can range from the current node value+1 to max.

Algorithm👽

• Make a variable temp, pop the node from the queue, and store it into temp.
   
• Now, check if the current element of the array can be a left child or right child of the node stored in temp with the help of min, max, and value of temp.
   
• Create a new node for this new array element with min and max properties and push it into the queue.
   
• Move to the next array element and repeat the previous steps till all the array elements are exhausted, or the queue becomes empty.
   
• If all the array elements are traversed, then this array can represent the level order traversal of BST; otherwise, it can not.

C++ Code:

//Program to Find if the given array 
//can represent Level Order Traversal of BST or not.
#include <bits/stdc++.h>


using namespace std;


// to store details of a node 
struct node
{
	int data;
	int min;
	int max;
};


// function to find if the given array 
//can represent Level Order Traversal of BST
// of Binary Search Tree
bool CanRepresent(int Arr[], int n)
{
	// nase case
	if (n == 0) return true;

	queue<node> queue;

	// index to traverse array elements
	int j=0;

	// node details for the
	// root of the BST
	node curr;
	curr.data = Arr[j++];
	curr.min = INT_MIN;
	curr.max = INT_MAX;
	queue.push(curr);

	// until there are no more elements
	// in Arr[] or queue is not empty
	while (j != n && !queue.empty())
	{
		node tmp = queue.front();
		queue.pop();

		// check whether there are more elements
		// in the arr[] and arr[i] can be left child
		// of 'tmp.data' or not
		if (j < n && (Arr[j] < tmp.data &&
		Arr[j] > tmp.min))
		{
			// Create NodeDetails for curr
			/// and add it to the queue
			curr.data = Arr[j++];
			curr.min = tmp.min;
			curr.max = tmp.data;
			queue.push(curr); 
		}

		// check whether there are more elements
		// in the Arr[] and Arr[i] can be right child
		// of 'tmp.data' or not
		if (j < n && (Arr[j] > tmp.data &&
		Arr[j] < tmp.max))
		{
			curr.data = Arr[j++];
			curr.min = tmp.data;
			curr.max = tmp.max;
			queue.push(curr); 
		}
	}

	return j==n;
}


// Driver program to test above
int main()
{
	int Arr[] = {8, 5, 13, 4, 7, 9, 2, 6, 11};
	int n = sizeof(Arr) / sizeof(Arr[0]);
	if (CanRepresent(Arr, n))
	cout << "Yes";
	else
	cout << "No";
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

Yes

JAVA Code:

//Program to Find if the given array 
//can represent Level Order Traversal of BST or not.
import java.util.*;


class Solution
{

	// to store details of a node 
	static class node
	{
		int data;
		int min;
		int max;
	};
	// function to find if the given array 
	//can represent Level Order Traversal of BST
	// of Binary Search Tree
	static boolean CanRepresent(int arr[], int n)
	{
		// base condition
		if (n == 0) return true;


		Queue<node> queue = new LinkedList<node>();

		// index to traverse array elements
		int j = 0;

		// node details for the
		// root of the BST
		node curr=new node();
		curr.data = arr[j++];
		curr.min = Integer.MIN_VALUE;
		curr.max = Integer.MAX_VALUE;
		queue.add(curr);

		// until there are no more elements
		// in Arr[] or queue is not empty
		while (j != n && queue.size() > 0)
		{
			// extracting NodeDetails of a
			// node from the queue
			node tmp = queue.peek();
			queue.remove();
			curr = new node();

			// check whether there are more elements
			// in the arr[] and arr[i] can be left child
			// of 'tmp.data' or not
			if (j < n && (arr[j] < (int)tmp.data &&
			arr[j] > (int)tmp.min))
			{
			// Create NodeDetails for curr
			// and add it to the queue
			curr.data = arr[j++];
			curr.min = tmp.min;
			curr.max = tmp.data;
			queue.add(curr); 
			}

			curr=new node();

			// check whether there are more elements
			// in the Arr[] and Arr[i] can be right child
			// of 'tmp.data' or not
			if (j < n && (arr[j] > (int)tmp.data &&
			arr[j] < (int)tmp.max))
			{
				// Create NodeDetails for newNode
				/// and add it to the queue
				curr.data = arr[j++];
				curr.min = tmp.data;
				curr.max = tmp.max;
				queue.add(curr); 
			}
		}

		return j==n;
	}


	// main
	public static void main(String args[])
	{
		int arr[] = {550, 250, 140, 550, 150};
		int n = arr.length;
		if (CanRepresent(arr, n))
		System.out.print( "Yes");
		else
		System.out.print( "No");

	}
}

You can also try this code with Online Java Compiler

Run Code

Output: 

No

Complexity Analysis

Time Complexity: O(N), where N is the size of a given array. We traverse the whole array, which takes O(N) time.

Space Complexity: O(N), We use a queue data structure to store array elements.

Check out this problem - Duplicate Subtree In Binary Tree