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














































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[0]);

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;
}

Comments