Oracle Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
This is the solution to your question, plus it returns the total count of nodes for the given node. Hope that the code is self explaining. :)
struct Node {
Node *left;
Node *right;
int leftcount;
int rightcount;
};
int node_count(Node *pNode)
{
int l = 0;
int r = 0;
if (NULL == pNode)
return 0;
if (pNode->left) {
l = 1 + node_count(pNode->left);
pNode->leftcount = l;
}
else {
pNode->leftcount = 0;
}
if (pNode->right) {
r = 1 + node_count(pNode->right);
pNode->rightcount = r;
}
else {
pNode->rightcount = 0;
}
return l + r;
}
// please tell me mistake in this algo..
int nodes(struct *node)
{
if(node==NULL)
return 0;
ans=nodes(node->left)+nodes(node->right)+1;
return ans;
}
// please tell me mistake in this algo..
int nodes(struct *node)
{
if(node==NULL)
return 0;
ans=nodes(node->left)+nodes(node->right)+1;
return ans;
}
// please tell me mistake in this algo..
int nodes(struct *node)
{
if(node==NULL)
return 0;
ans=nodes(node->left)+nodes(node->right)+1;
return ans;
}
In the question mentioned above, we have to populate the no,of nodes in LHS and RHS of the binary tree. But in your algorithm you are simply returning the total count of the nodes. The algorithm is not able to distinguish the no,of nodes present in the RHS or LHS neither is it storing it in the data field.
the problem can be removed by using
int update_parameters(tree* node)
{
if(node==NULL)
return 0;
node->left_child=update_parameters(node->child[0]);
node->right_child=update_parameters(node->child[1]);
return node->left_child+node->right_child+1;
}
My answer
#include "stdafx.h"
struct Tree
{
int data;
int lCount;
int rCount;
Tree *left;
Tree *right;
};
Tree * CreateTree(Tree *root, int value)
{
if(root == NULL)
{
root = new Tree();
root->data = value;
root->left = NULL;
root->right = NULL;
root->lCount = 0;
root->rCount = 0;
}
else if(value < root->data)
root->left = CreateTree(root->left, value);
else
root->right = CreateTree(root->right, value);
return root;
}
Tree * CountLR(Tree *root)
{
Tree *node = NULL;
if(root != NULL)
{
if(root->left == NULL && root->right == NULL)
{
root->lCount = 0;
root->rCount = 0;
}
else if(root->left == NULL)
{
root->lCount = 0;
node = CountLR(root->right);
root->rCount = node->rCount + node->lCount + 1;
}
else if(root->right == NULL)
{
root->rCount = 0;
node = CountLR(root->left);
root->lCount = node->lCount + node->rCount + 1;
}
else
{
node = CountLR(root->left);
root->lCount = node->lCount + node->rCount + 1;
node = CountLR(root->right);
root->rCount = node->rCount + node->lCount + 1;
}
}
return root;
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[] = {30,15,10,66,51,53,12};
Tree *root = NULL;
for(int i=0; i< 7; i++)
root = CreateTree(root, arr[i]);
CountLR(root);
return 0;
}
Tree* Count(Tree *root)
{
if(root != NULL)
{
if(root->left == NULL)
root->lCount = 0;
if(root->right == NULL)
root->rCount = 0;
if(root->left)
root->lCount = Count(root->left)->lCount + Count(root->left)->rCount + 1;
if(root->right)
root->rCount = 1 + Count(root->right)->lCount + Count(root->right)->rCount;
}
return root;
}
this might also be one of the answers
struct node
{
int lcount;
int rcount;
struct node * left;
struct node * right;
};
typedef struct node NODE;
NODE * populate( NODE * root)
{
if(!root)
return 0;
root->lcount=populate(root->left);
root->rcount=populate(root->right);
return(root->lcount+root->rcount+1);
}
This is what solution I came up with:
- rising April 15, 2012void populate(NODE *root){ if (root == NULL) return; populate(root->left); populate(root->right); if(root->left) root->lc = root->left->lc + root->left->rc + 1; else root->lc = 0; if(root->right) root->rc = root->right->lc + root->right->rc + 1; else root->rc = 0; }