Exactly One Child

Easy
0/40
Average time to solve is 15m
14 upvotes
Asked in company
Lenskart.com

Problem statement

You are given an array/list ‘ARR’ representing pre-order traversal of a Binary Search Tree (BST). If each non-leaf node of the tree has only one child, then return true otherwise, return false.

A binary search tree (BST) is a binary tree data structure with the following properties:

• The left subtree of a node contains only nodes with data less than the node’s data.

• The right subtree of a node contains only nodes with data greater than the node’s data.

• Both the left and right subtrees must also be binary search trees.


Assume that the BST contains unique entries.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of the input contains an integer ‘N’ representing the size of the array.

The second line of the input contains ‘N’ space-separated integers representing elements of the array ‘ARR’.
Output Format : 
For each test case, print a string ‘S’ denoting if each non-leaf node of the tree has only one child or not. If each non-leaf has only one child then ‘S’ will be “true”, otherwise “false”.

Output for each test case will be printed in a separate line.
Note 
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 20
1 <= N <= 10^4
1 <= ARR[i] <= 10^5

Time Limit: 1 sec
Sample Input 1:
2
1
10
5
20 10 11 13 12
Sample Output 1:
true
true
Explanation For Sample Output 1:
In the first test case, there is only one node. So the output will be true.

In the second test case, all the elements right to 20 are less than 20, so all of them must be in the left tree.

Similarly, all the elements next to 10 are greater than 10, so all of them must be in the right subtree, and so on.

Hence the output will be true.
Sample Input 2:
2
3
10 11 12
4
25 29 24 26
Sample Output 2:
true
false
Hint

Observe a pattern in pre-order traversal of a BST in which non-leaf nodes have only one child. Can you think of a solution by this observation?

Approaches (2)
Brute force

In preorder traversal, we first visit the root node, then the left sub-tree, and then the right subtree. So all the descendants of a Node appear on the right in the pre-order traversal.

 

If a particular node has only one child, then all the descendants are either on the right subtree or left subtree. Hence the descendants are either all greater than the node or all less than the Node.

 

The steps are as follows:

 

  1. Declare a variable ‘FLAG’ of type boolean, to check if all numbers right to an element is either greater or lesser.
  2. Iterate the array ‘ARR’ from ‘0’ to ‘N’ - 1. (say, the iterator be ‘i’ )
    1. If ‘ARR[i+1]’  is greater than ‘ARR[i]’, then update the ‘FLAG’ to true.
    2. Else update ‘FLAG’ to false.
    3. Iterate ‘ARR’ from ‘i’ + 1 to ‘N’. (say, the iterator be ‘j’).
      1. If ‘FLAG’ is true and ‘ARR[j]’ is less than ‘ARR[i]’  or ‘FLAG’ is false and ‘ARR[j]’ is greater than ‘ARR[i]’, then return false.
  3. Otherwise, return true.
Time Complexity

O(N^2), where ‘N’ is the number of elements in the given array.

 

We are checking the pattern for all right elements of each element. For this, we have to iterate through the array twice. Hence, the overall complexity is O(N^2).

Space Complexity

O(1).

 

Constant extra space is used.

Code Solution
(100% EXP penalty)
Exactly One Child
Full screen
Console