A FULL node in a binary tree is a node that has exactly two non-null children. Write a RECURSIVE function that returns the number of full nodes in a binary tree.
# include <iostream >
#include <stdio.h >
using namespace std;
struct TreeNode{
int value;
TreeNode* left;
TreeNode* right;
};
int FullNodes(TreeNode* root){
if(root == NULL) //if tree is empty
return 0;
if(root->left == NULL && root->right == NULL) //leaf nodes
return 0;
if(root->left!=NULL && root->right != NULL) // Full Nodes
return 1 + FullNodes(root->left) + FullNodes(root->right);
if(root->left==NULL && root->right != NULL) //Nodes with no left child
return FullNodes(root->right);
if(root->left!=NULL && root->right == NULL) // Nodes with no right child
return FullNodes(root->left);
}
/*---------------------------------TEST---------------------------------*/
//Function to insert into binary tree
void insert(TreeNode*& root, int num){
if(root == NULL){
root = new TreeNode();
root->value = num;
root->left = NULL;
root->right = NULL;
}
else if(num < root->value){
insert(root->left,num);
}
else
insert(root->right,num);
}
int main(){
//creates a tree
TreeNode* tree = NULL;
insert(tree, 8);
insert(tree, 5);
insert(tree,10);
insert(tree, 3);
insert(tree, 9);
insert(tree, 6);
//Full Node count test
cout << FullNodes(tree); //8 and 5 are full nodes . So output is 2
return 0;
}
This comment has been removed by the author.
ReplyDeleteHi.. I am getting error 'count_odd' was not declared in this scope. Can someone please help me out with this. This code count the number of odd nodes in a tree.
ReplyDelete#include
using namespace std;
class Node{
public:
int _key;
Node* left;
Node* right;
Node(int key): _key(key),left(NULL),right(NULL){}
Node(int key,Node* left,Node* right):_key(key),left(left),right(right){}
int count_odd(int, Node*);
};
int Node::count_odd(int count, Node *a)
{
int temp=0;
if(a!=NULL)
{
if((a->_key%2)!=0)
count++;
count=count_odd(temp, a->left)+count_odd(temp, a->right);
}
return count;
}
int main()
{
Node* root=new Node(3);
root->left=new Node(5);
root->left->left=new Node(8);
root->right=new Node(7);
root->right->left=new Node(5);
root->right->right=new Node(2);
cout<_key<left->_key<left->left->_key<right->_key<right->left->_key<right->right->_key<<endl;
int t=count_odd(0, root);
cout<<"total no of odd nodes "<<t;
return 0;
}