MCN Professionals | Interview Question of the day
MCN Professionals is starting Industrial Training for MCA-2012 Batch. Have a look at our Industrial Training Program and Course Details.
-----------------------------------------------------------------------------------------------------------------------------------------
Today's Question:
Write a function that will return the number of non-leaf nodes in a binary tree.
For example: In the below binary tree
Has 3 leaf nodes (C, D & E) and 2 non-leaf nodes(A & B).
Solution:
Algorithm:
If (current node is a leaf node or it is NULL)
return 0;
else
return (1 + non_leaf_count of left sub tree + non_leaf_count of right sub tree);
C Program: Here is a C program to do the same..
struct Node{
int data;
Node* lptr;
Node* rptr;
}
/** return the number of non-leaf nodes in the tree whose root is at r */
int count_non_leaf(Node *r){
/* If r is either leaf node or NULL */
if(r==NULL || (r->lptr == NULL && r->rptr == NULL) ){
return 0;
}else{
return (1 + count_non_leaf(r->lptr) + count_non_leaf(r->rptr) );
}
}
---------------------------------------------------------------------------
Interview Questions Archive:
To see all the questions in the category click
here...