ADVERTISEMENT
ADVERTISEMENT

Check if the given array can represent inorder traversal of a BST

In this article, we are going to see how to check if the given array can represent inorder traversal of a BST?
Submitted by Radib Kar, on November 01, 2020

In this article, we are going to see how to find whether a given array can represent inorder traversal of a BST or not. As we already know that inorder traversal of a Binary Search Tree produces a sorted list which is strictly increasing. So if an array can represent inorder traversal for a BST, then it has to be strictly increasing. So, we just need to check whether the array is strictly increasing or not.

For example,

[3, 10, 13, 16, 18, 20]

Is a strictly increasing array and thus it can represent inorder traversal of a Binary search tree. Below is the create BST.

Check if the given array can represent inorder traversal of a BST

But if the given array is [3, 2] or if it's [2, 2, 4] then it's not a valid representation of BST inorder traversal.

Below is the C++ implementation:

#include <bits/stdc++.h>
using namespace std;

//function which returns true if it's a valid inorder 
//traversal for a BST, else return false
int isInorderTraversal(vector<int> a, int n)
{
    //base case, a NULL tree or a single node is always a BST
    if (n == 0 || n == 1)
        return true;
    //check if it's a sorted list(strictly increasing only)
    for (int i = 0; i < n - 1; i++) {
        if (a[i] >= a[i + 1])
            return false;
    }

    return true;
}

int main()
{
    int t, n, item;

    cout << "Enter number of elements in the list" << endl;
    cin >> n;

    cout << "Enter the elements" << endl;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    bool result = isInorderTraversal(arr, n);

    if (result)
        cout << "This array is a valid inorder traversal for a BST" << endl;
    else
        cout << "This array is an invalid inorder traversal for a BST" << endl;

    return 0;
}

Output:

RUN 1:
Enter number of elements in the list
6
Enter the elements
3 10 13 16 18 20
This array is a valid inorder traversal for a BST

RUN 2:
Enter number of elements in the list
2
Enter the elements
3 2
This array is an invalid inorder traversal for a BST
ADVERTISEMENT



ADVERTISEMENT



Comments and Discussions


ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.