Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \ / \ 4 5 6 7 The tree has 5 vertical lines Vertical-Line-1 has only one node 4 => vertical sum is 4 Vertical-Line-2: has only one node 2=> vertical sum is 2 Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12 Vertical-Line-4: has only one node 3 => vertical sum is 3 Vertical-Line-5: has only one node 7 => vertical sum is 7 So expected output is 4, 2, 12, 3 and 7
Printing Downwards Path ->
ReplyDeletefunc(root,p,k)
{
if(!root || !p ) return;
if(k==0) print(root->data);
else{ func(root,p->left,k-1);
func(root,p->right,k-1);
}
}
Printing Upwards Path and inverted-V type paths : -
we can do inorder DFS to find the node and keep track of depth,
if node is found,it contains nodes from root to p in stack.
We can pop every node from stack and for ith node popped from stack,call (k-i)distance downwards nodes recursively in the other subtree.
Please check.
typedef struct node
ReplyDelete{
int data;
struct node *left;
struct node *right;
}node;
void printkdistanceNodeDown(node *n, int k)
{
if(!n)
return ;
if(k==0)
{
printf("%d\n",n->data);
return;
}
printkdistanceNodeDown(n->left,k-1);
printkdistanceNodeDown(n->right,k-1);
}
void printkdistanceNodeDown_fromUp(node* target ,int *k)
{
if(!target)
return ;
if(*k==0)
{
printf("%d\n",target->data);
return;
}
else
{
int val=*k;
printkdistanceNodeDown(target,val-1);
}
}
int printkdistanceNodeUp(node* root, node* n , int* k)
{
if(!root)
return 0;
if(root->data==n->data)
return 1;
int pl=printkdistanceNodeUp(root->left,n,k);
int pr=printkdistanceNodeUp(root->right,n,k);
if(pl )
{
(*k)--;
if(*k==0)
printf("%d\n",root->data);
else
printkdistanceNodeDown_fromUp(root->right,k);
return 1;
}
if(pr )
{
(*k)--;
if(*k==0)
printf("%d\n",root->data);
else
printkdistanceNodeDown_fromUp(root->left,k);
return 1;
}
return 0;
}
void printkdistanceNode(node* root, node* n , int k )
{
if(!root)
return ;
int val=k;
printkdistanceNodeUp(root,n,&k);
printkdistanceNodeDown(n,val);
}
caller function : printkdistanceNode(root,n,k);
output will print all the nodes at a distance k from given node upward and downward.
@Anonymous please explain your approach..
ReplyDeleteOnce we find the the given node ,
Delete1>we traverse forward to find all k distance nodes.That is easy.
2>also we traverse backward k distance to find k distance node .
Please note : if we traverse backward and value is less than k for any backward node then we have to traverse down from that node opposite side from where it is coming(i.e if traverse backward is from left subtree than we have to traverse right ).
though my solution doesnt print o/p as desired FORMAT as asked but it prints ALL k distance node from a given node.
check this code with long binary tree .
@admin : i hope this explaination helps.
good collections of question :)
This comment has been removed by the author.
ReplyDelete