Amazon Interview Question
Country: India
Interview Type: In-Person
for(int i=0;i++;i<n)
{
count=count+rollUpTree(root.children(i));
}
hey what is "n" here?
Answer in C
==========
Lets there is n-ary Tree
#define CHILD (n)
struct node
{
int data;
int childCount;
node * childrens[CHILD];
};
int rollUpTree(node *root)
{ int i=0,nodeData=0;
if(root==NULL)
return -1;
if(root->childCouor(intnt==0)
{
return root->data;
}
else
{
nodeData=root->data;
for(i=0;i< root->childCount;i++)
{
nodeData = nodeData + rollUpTree(root->children[i]);
}
root->data=nodeData;
return nodeData;
}
}
This is not a exact roll up of the tree. Reverse BSF order must be followed. The sum of node values in level n is added to nodes in level n-1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/*
Given an n-ary tree (i.e. it can have max n children).
One need to roll up the tree from leaves back to root such that the
data of root will be the sum of root's data and sum of all its children data
*/
namespace Fundey_ReverseBFS
{
class Node
{
public Int32 data;
public Int32 childSum;
public List<Node> arr = new List<Node>();
public Node(Int32 d)
{
this.data = d;
}
}
class Program
{
static void Main(string[] args)
{
Node n1 = new Node(10);
Node n2 = new Node(20);
Node n3 = new Node(30);
Node n4 = new Node(40);
Node n5 = new Node(50);
Node n6 = new Node(60);
n1.arr.Add(n2);
n1.arr.Add(n3);
n2.arr.Add(n4);
n2.arr.Add(n5);
n3.arr.Add(n6);
GetChildSum(n1);
Console.ReadLine();
}
public static Int32 GetChildSum(Node root)
{
Int32 sum=0;
if (root == null)
return 0;
//Int32 sum = GetChildSum(root.left) + GetChildSum(root.right) + root.data;
Int32 childNum = 0;
while (root.arr.Count >0 && childNum < root.arr.Count)
{
sum = sum + GetChildSum(root.arr[childNum]);
childNum++;
}
sum = sum + root.data;
root.childSum = sum;
Console.WriteLine("Node = " + root.data + " Child level sum = " + (sum - root.data));
return sum;
}
}
}
This piece of code should sum up the childrem to root. the questions sounds simple. Am I missing something?
public void sumTreeNodes (Node n) {
sum = sum + n.getValue();
if (n.getNodeList()!= null && n.getNodeList().size() > 0) {
for (Node node: n.getNodeList()) {
sumTreeNodes (node);
}
}
}
we can do it through modified postorder traversal
int postorder(struct node *head,int sum)
{
if(head != NULL)
{
int s1= postorder(head->left,sum);
int s2= postorder(head->right,sum);
head->data = s1+s2+ head->data;
return(node->data);
}
return 0;
}
call(root,0) from main.. i hope i am clear in explaining
class NAryNode
- Vyshnavi June 10, 2012{
int data;
ArrayList<Integer> children;
NAryNode(int data)
{
this.data=data;
children=new ArrayList<Integer>(GIVEN_INT);
}
}
int rollUpTree(NAryNode root)
{
if(root == null)
return -1;
if(root.children.size()==0)
return root.data;
int count=root.data;
for(int i=0;i++;i<n)
{
count=count+rollUpTree(root.children(i));
}
return count;
}