Last Updated: 3 Dec, 2020

Exactly One Child

Easy

Asked in company

Solve now

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.

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

Solve now

Approaches

01 Approach

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:

Declare a variable ‘FLAG’ of type boolean, to check if all numbers right to an element is either greater or lesser.
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.
Otherwise, return true.

Solve now

02 Approach

In this approach, we will take the last two elements of the array. Set the lesser one as ‘MIN’ and the greater one as ‘MAX’. Now each element should be lesser than ‘MIN’ and greater than ‘MAX’. We will keep updating ‘MAX’ and ‘MIN’ accordingly.

The steps are as follows:

Declare two-variable ‘MIN’ and ‘MAX’ of type integer.
If ‘ARR[N - 1]’ is greater than ‘ARR[N - 2]’, then update ‘MAX’ as ‘ARR[N - 1]’ and ‘MIN’ as ‘ARR[ N - 2]’.
Else if ‘ARR[N - 2]’ is greater than ‘ARR[N - 1]’, then update ‘MAX’ as ‘ARR[N - 2]’ and ‘MIN’ as ‘ARR[ N - 1]’.
Iterate in ‘ARR’ in reverse from ‘N’ - 3 to 0. (say, the iterator be ‘i’ ).
1. If ‘ARR[i] is less than ‘MIN’, then update ‘MIN’ as ‘ARR[i]’.
2. Else if ‘ARR[i]’ is greater than ‘MAX’, then update ‘MAX’ as ‘ARR[i]
3. Else return false..’
Return true.

Solve now