Question

Given a pointer to a binary tree write a routine which will traverse the tree and return number of nodes in the tree who have just a right son or just a left son (do not include nodes have both right and left sons as well as do not include any nodes that do not have any sons at all).

Answer 1

#include <iostream>
#include <stdlib.h>
using namespace std;

typedef struct node
{
int data;
struct node *left, *right;
}btree;

btree* addNode(int val)
{
   btree* newNode = new btree;
   newNode->data = val;
   newNode->left = NULL;
   newNode->right = NULL;
   return newNode;
}

int countSingleChild(btree* root)
{
   if(root == NULL)
       return 0;
   else if(root->left == NULL && root->right != NULL)
       return 1 + countSingleChild(root->right);
   else if(root->left != NULL && root->right == NULL)
       return 1 + countSingleChild(root->left);
   else
       return countSingleChild(root->left) + countSingleChild(root->right);
}

int main()
{
  
   btree* root = addNode(1);
   root->left = addNode(2);
   root->right = addNode(3);
   root->left->left = addNode(4);
   root->left->right = addNode(5);
   root->left->right->right = addNode(6);
   root->right->right = addNode(7);
   root->right->right->right = addNode(8);
   root->right->right->right->left = addNode(9);

   cout << "Number of single childs are : " << countSingleChild(root) << endl;
   return 0;
}

Terminal OpenF splitList.cpp LL1.0pp treeSinglechild.cpp #1nclude <tos trees Lnclude <stdlib. h using nanespace std; typedef struct node int date; struct node eft, right sasigsasi-desktop: /Desktop/pro/c sastesasi-desktop: /Desktop/pro/C++$ /treesinglochtld unber of stngle childs are4 sastgsast-desktop: Desktop/pro/c++$I btree: btree addNode(int val) btre* newade-new btron; newNode-data val; ne«Node->left = NULL; newNode-right NULL; return newode int countsingleChild(btree root) if(root NULL else if(rootゥLeft else if(root-left return return 1 +countsinglechild(root-right) return 1countsinglcchtld(root left) return count5inglechtldrootleft) countstnglechtld(root-right); ". NULL && raotウright !-NULL) !ㅡ NIJI I &R root-right --NULI) btree* foot-addNode1): root-ン1ert - eddNode( 2); root->right - eddNode(3); raot-left-left addNode(4); raot->1eft-right - addNode(s); raot->left-right-right -add Nade() raot-right right addNade(); raot right right right addNode(8); root-rtght right rtght-loft-addNode() cout < "Nuber ot single chtlds are "< countsinglechtld(root) << endl; return θ; C++▼ Tab width: B▼ Ln 9, Col 24 ▼ INS