Question

(Binary Tree): Write a recursive implementation of the function, singleParent, that returns the number of the nodes in a binary tree that have only one child. Convert it to an iterative version. in C++

Answer 1

Solution:

Recursive implementation of the function singleParent:

// C++ program to count number of the nodes in a binary tree that have only one child

#include <bits/stdc++.h>

using namespace std;

//node structure that have data, left and right pointer

struct Node

{

int data;

struct Node* left, *right;

};

// Recursive function to get the count of half Nodes

unsigned int singleParent(struct Node* root)

{

if (root == NULL)

return 0;

int res = 0;

if ((root->left == NULL && root->right != NULL) ||

(root->left != NULL && root->right == NULL))

res++;

res += (singleParent(root->left) + singleParent(root->right));

return res;

}

struct Node* newNode(int data)

{

struct Node* node = new Node;

node->data = data;

node->left = node->right = NULL;

return (node);

}

// Driver program

int main(void)

{

struct Node *root = newNode(2);

root->left = newNode(7);

root->right = newNode(5);

root->left->right = newNode(6);

root->left->right->left = newNode(1);

root->left->right->right = newNode(11);

root->right->right = newNode(9);

root->right->right->left = newNode(4);

cout << singleParent(root);

return 0;

}

Iterative implementation of the function singleParent:

// C++ program to count number of the nodes in a binary tree that have only one child

#include <bits/stdc++.h>

using namespace std;

//node structure that have data, left and right pointer

struct Node

{

int data;

struct Node* left, *right;

};

// recursive function to count number of the nodes in a binary tree that have only one child

unsigned int singleParent(struct Node* node)

{

// If tree is empty

if (!node)

return 0;

int count = 0; // Initialize count of half nodes

// Do level order traversal starting from root

queue<Node *> q;

q.push(node);

while (!q.empty())

{

struct Node *temp = q.front();

q.pop();

if ((!temp->left && temp->right) || (temp->left && !temp->right))

count++;

if (temp->left != NULL)

q.push(temp->left);

if (temp->right != NULL)

q.push(temp->right);

}

return count;

}

struct Node* newNode(int data)

{

struct Node* node = new Node;

node->data = data;

node->left = node->right = NULL;

return (node);

}

// Driver program

int main(void)

{

//create bianry tree

struct Node *root = newNode(2);

root->left = newNode(7);

root->right = newNode(5);

root->left->right = newNode(6);

root->left->right->left = newNode(1);

root->left->right->right = newNode(11);

root->right->right = newNode(9);

root->right->right->left = newNode(4);

cout << singleParent(root);

return 0;

}

Please give thumbsup, if you like it. Thanks.