Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
This assumes a binary tree, but can easily be modified to work for n-ary trees and seems like it will work.
Of course, the code is not that great.
Some comments:
1) Redundant includes.
2) Unnecessary declarations.
3) system("pause"): Yuck!
4) Having printf deep in the bfs code.
5) Possibly more, but the above stand out.
Here is my implementation in C++:
basicalgos.blogspot.com/2012/04/39-print-nodes-tree-level-by-level.html
Nice code ...
Thank you for the solution
I used your code, where the input is given by the user itself and the tree is created as per users choice.
BFS works like this. It checks elements which are at 0 to h hops away, where h is height of the tree. So when you start with the root, print the node which at 0 distance from the root (which is the root itself). Then print the nodes which are at 1 hop distance (nothing but the children i.e level 1) and so on.
Traverse the tree as usual but keep track of which level you are on in the tree. If you are using a recursive method then pass a variable for level. Also pass a HashMap with key as level number and value as list of nodes on that level
Suggested method signature:
void levelOrderTraversal(Node node, int level, Map<Integer, List<Node>>)
Code for the same logic. Only, hashmap is a class variable, no need to pass it as parameter.
nodesByLevel is the hashmap being used, initialized outside the method.
Pass printElementsInEachLevel (rootNode, 0) ;
public static void printElementsInEachLevel (Node node, int level)
{
if (node == null)
return;
List<Node> lst = nodesByLevel.get(level);
if (lst == null)
lst = new ArrayList<Node>();
lst.add(node);
nodesByLevel.put(level, lst);
printElementsInEachLevel (node.left, level + 1);
printElementsInEachLevel (node.right, level + 1);
}
void printtree(queue<Node*>& qq)
{
if (qq.size()==0) {
return;
}
queue<Node*> mqq;
while (qq.size()) {
Node* temp=qq.front();
qq.pop();
cout << temp->data << ' ';
if (temp->child) {
temp=temp->child;
mqq.push(temp);
while (temp->sib) {
temp=temp->sib;
mqq.push(temp);
}
}
}
cout << endl;
printtree(mqq);
}
level order traversal:
const int d=depth(root);
for (int i = 0; i <d;++i) {
PrintLevel(root, i);
std::cout << std::endl;
}
PrintLevel(NODE* root, int d) {
if (!root) return;
if (d==0) {
std::cout << root->data;
return;
}
PrintLevel(root->left, d-1);
PrintLevel(root->right, d-1);
}
Print Tree by level (root)
Queue q
int curCount = 0, nextCount =0
//add root in queue
if ( root)
q.push(root)
++nextCount
while (!q. empty )
curCount = nextCount
nextCount = 0;
print ( node in level :: )
//print all node in current level
while (curCount--)
node n = q.pop();
//add left child in queue if not null
if (n->left)
q.push(n->left)
++ nextCount;
//add right child in queue if not null
if (n->right)
q.push(n->right)
++ nextCount
print (n)
Thats Level Order Traversal
Below is the code
- Anurag Gupta April 05, 2012#include <set> #include <queue> #include <stack> #include <list> #include <algorithm> #include <vector> #include <cmath> #include <cstdio> #include <iostream> #include <cstring> #include <cstdlib> #include <unistd.h> using namespace std; typedef unsigned long long ULL; # define MOD 1000000007 struct node { int data; node *left, *right; }; node *newnode(int data) { node *p; p = new node; p->data = data; p->left = p->right = NULL; return p; } void levelOrder(node *root) { queue < node* > Q; int currentLevelNodes = 1; int nextLevelNodes = 0; int spiral = 0; node *curr; Q.push(root); while ( ! Q.empty() ) { curr = Q.front(); Q.pop(); printf("%d ", curr->data); currentLevelNodes--; if (curr->left != NULL) { Q.push(curr->left); nextLevelNodes++; } if (curr->right != NULL) { Q.push(curr->right); nextLevelNodes++; } if (currentLevelNodes == 0) { printf("\n"); currentLevelNodes = nextLevelNodes; nextLevelNodes = 0; } } } int main() { node *root; root = newnode(1); root->left = newnode(4); root->right = newnode(5); root->left->left = newnode(2); root->left->right = newnode(3); root->right->left = newnode(7); root->right->right = newnode(8); root->left->left->left = newnode(10); root->left->right->right = newnode(15); root->right->right->left = newnode(14); root->right->right->right = newnode(20); levelOrder(root); system("pause"); return 0; }