Binary Search Trees: Given a BST, check if each internal node has only one child

Problem Statement:

You are given an array in pre-order traversal of BST.
You need to check if non leaf node has only one child.
BST will have unique entries.

BST is a tree that satisfies below condition:

1. Left subtree will have the node less than the node key

2. Right subtree will have the node greater than the node key

3. Duplicate values are not allowed

Example:

Input:
arr[] = {30, 20, 21, 23, 22 }

Output: Yes

Explanation:

From the below image, we can see that each node has only one child and the tree is BST

Solution 1: Bruteforce Approach

We will use pre order traversal to solve the problem.

In PreOrder traversal, we will visit the root node, followed by left and right sub tree.

If any node has only one child, then all the descendants are either on right sub tree or left sub tree.

Hence the descendants are either all greater than the node or all less then the node.

So in this case, for each node [i] all nodes should be either lesser or greater than the current node.

If the condition is true, return true else false.

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2: Efficient approach

All the descendants of the node should either be smaller or larger, then we can follow below steps:

For a node, get the next pre order successor and last preorder successor and check if both are either greater or smaller and return true.

Else, if the current node has both left and right subtree, and one element is smaller than the current node and another is greater than the current node, return false.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include<iostream> 
#include<vector> 
using namespace std; 

bool solution_1(vector<int> preorder)
{
    bool is_large;

    for(int i=0; i < preorder.size(); i++)
    {
        if(preorder[i+1] > preorder[i])
            is_large = true;
        else
            is_large = false;

        for(int j=i+1; j<preorder.size(); j++)
            if( (is_large && preorder[j] < preorder[i]) || (!is_large && preorder[j] > preorder[i]) )
                return false;
    }
    return true;
}


bool solution_2(vector<int> preorder)
{
    int len = preorder.size();

    int next_diff, last_diff;

    for(int i = 0; i < len; i++)
    {
    	next_diff = preorder[i] - preorder[i+1];
        last_diff = preorder[i] - preorder[len-1];

        if (next_diff*last_diff < 0)
            return false;;

    }

    return true;
}



int main() {
    vector<int> arr = { 30, 20, 21, 23, 22 };
    
    if (solution_1(arr))
        cout << "True";
    else
        cout << "False";
    cout<<endl;
    if (solution_2(arr))
        cout << "True";
    else
        cout << "False";
             
  return 0;
}

Output

True
True