 ### C++ program to check if each internal node of a binary search tree has exactly one child

Binary Search Tree(BST) :
A binary search tree structure is a recursive tree structure. It is possible to define a tree of a given size in terms of smaller tree which exhibit the tree like properties.This recursive nature of tree has important implications in relation.
BinarySearchTree is a tree with some specifications:

1.A BST must have atmost one left child (Smaller than the value of parent root)
2.A BST mush have atmost one right child (Greater tan the value of the parent root)

The element which is less than the root ( root  > child  )becomes the left child.
The element which is greater than the root ( root  < child )becomes the right child. Image -->Binary Search Tree

PROGRAM STATEMENT --------> C++ program to check if each internal node of a binary search tree has exactly one child.
INPUT:     { 8  ,   21  ,  18  ,  20  ,   19  }
OUTPUT:                 If True:        The Internal nodes of BST  (Binary Search Tree) have only one child
If False:        The Internal nodes of BST(Binary Search Tree) have more than one child Image -->Binary Search Tree with internal node having One Child

ALGORITHM :

1.Initialse two nested loops i = 0 to n (Outer loop)
j = i+1 to n (Inner loop)

2. The outer loop starts from the first element and the inner loop checks if all elements are greater or smaller than the first node.

binarytree[ i ] ---> binarytree[ i+1 ] , binarytree[ i+2 ] .....binarytree[ i+n ]

3 .While Step 2 is true, the outer loop is incremented to the next element
4.If Step 2 is false, break the loop and return false as the binary search tree has more than one child

i = 0 ---------> j = 1 , 2 , 3 , 4 ........n
i = 1 ---------->j = 2 , 3, 4 , 5........n
i = 2 ---------->  =3 , 4, 5  , 6.........n
|
|
|
n

`#include <bits/stdc++.h>using namespace std;bool BSTONECHILD(int binarytree[], int n){         //first loop to check the corresponding element with all the succesive elements   int i;   for (i=0 ; i<n ; )  //increament done inside the inner loop     {      int j=i+1; //Inner loop starts from the next element immediately`
`              // after corresponding element        if(binarytree[i]<binarytree[j])   {      while(binarytree[i] < binarytree[j] && j<n)  //checking if all the other `
`           //element are greater than the corresponding element --> arr[i]`
`      {         j++;      }      if (j==n)         i++;      else         return false;   }      else   {      while(binarytree[i] > binarytree[j] && j<n)     //checking if all the other `
`         //element are smaller than the corresponding element --> arr[i]      {         j++;      }      if (j==n)         i++;      else         return false;   }   }   if (i==n)   //if the both loops execute alternatively then the i value increases to n      return true;   else            //if both the loops does not execute alternatively then the`
`      return false;                 // function returns False      } //Execution starts from here int main() {   int binarytree[] =  {8 , 21 , 18 , 20 , 19} ;   int size = sizeof(binarytree)/sizeof(binarytree);   if (BSTONECHILD(binarytree,size) == true) //function call      cout<<"The Internal nodes of BST  (Binary Search Tree) have only one child.";   else      cout<<"The Internal nodes of BST(Binary Search Tree) have more than one child.";   return 0;}` #### More Articles of Smriti Pradhan:

Name Views Likes
C++ program to check if each internal node of a binary search tree has exactly one child 183 0