Amazon Interview Question
InternsCountry: India
Interview Type: Written Test
Varun,
Please help me to understand the logic?
I think we recursively go to each level until we find a null root, but what I am wondering is the exit condition.
When you find a null root, how can we print root->key??
So basically we keep going left until we find a leaf node rather than checking for null? In that case we print only left most leaf node?
Best Regards,
Sai
But, the requirement is leftmost at *each level*, not just the leftmost.
This sounds to me like it requires a bread-first search, but I'm not sure how to adapt that to keep track of the level the nodes are on, and don't really have time to think/solve atm.
This python might do it, test included:
import sys
class Node:
def __init__(self,data):
self.right = None
self.left = None
self.data = data
class Tracker:
def __init__(self,data,dist):
self.data = data
self.dist = float(dist)
def leftNodes(n,lvl,q,dist):
if n.left:
if len(q) < lvl + 1:
q.append(Tracker(n.left.data,dist))
elif q[lvl].dist > dist:
q[lvl] = Tracker(n.left.data,dist)
leftNodes(n.left,lvl + 1,q,dist)
if n.right:
if len(q) < lvl + 1:
q.append(Tracker(n.right.data,dist + 1.0/(lvl+1)))
elif q[lvl].dist > dist:
q[lvl] = Tracker(n.right.data,dist + 1.0/(lvl+1))
leftNodes(n.right,lvl + 1,q,dist + 1.0/(lvl+1))
def main():
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.left = Node(8)
root.right.left.right = Node(9)
root.right.left.right.left = Node(10)
root.right.left.right.right = Node(11)
q = []
leftNodes(root,0,q,0)
for i in q:
print i.data
if __name__ == "__main__":
sys.exit(main())
struct Node
{
int data;
struct Node *left;
struct Node *right;
struct Node *next;
};
struct Node *NewNode(int data)
{
struct Node *temp=(struct Node *)malloc(sizeof(struct Node));
temp->data=data;
temp->next=NULL;
temp->left=NULL;
temp->right=NULL;
return temp;
}
void LeftMostOnEachLevel(struct Node *&node)
{
if(!node)
return;
queue<struct Node *> myqueue;
myqueue.push(node);
myqueue.push(NULL);
while(true)
{
struct Node *temp=myqueue.front();
myqueue.pop();
if(temp)
{
temp->next=myqueue.front();
if(temp->right)
myqueue.push(temp->right);
if(temp->left)
myqueue.push(temp->left);
}
else
{
if(!myqueue.empty())
myqueue.push(NULL);
else
break;
}
}
}
void Traversal(struct Node *node)
{
if(!node)
return;
struct Node *temp=node;
while(temp->next)
temp=temp->next;
cout<<temp->data<<endl;
if(node->right)
Traversal(node->right);
else if(node->left)
Traversal(node->left);
}
int main()
{
struct Node *node=NewNode(1);
node->left=NewNode(2);
node->right=NewNode(3);
node->left->left=NewNode(4);
node->left->right=NewNode(5);
node->right->right=NewNode(6);
LeftMostOnEachLevel(node);
Traversal(node);
getchar();
return 0;
}
public static void printLeftNode(TreeNode pNode, HashMap<Integer, Boolean> map, int currenDepth){
if(pNode == null){
return;
}
if(!map.containsKey(currenDepth)){
System.out.print(pNode.data + " ");
map.put(currenDepth, true);
}
printLeftNode(pNode.pLeft, map, currenDepth + 1);
printLeftNode(pNode.pRight, map, currenDepth + 1);
}
I think at least we should traverse all the nodes in this tree, we cannot only keep the information of a single node in each level because if this node do not have child nodes then we have to look for other nodes who have child nodes at this level. My strategy is to print each level of this tree with 2 queues( 1 queue also works). The running time is O(n). Please let me know if there is a O(log(n)) solution.
do a travelsal on the tree and record the level when each node get visited. If this node is the first node get visited on this level, then this node is the leftmost node.
void visit(Node *node, int level) // level=0 at the time of invocation
{
if(b == NULL)
return;
else
{
if(map[level] == false)
{
map[level] = true
printf("Level:%d, Value%d\n", level, node->data)
}
visitLeft(node->left,level+1);
visitRight(node->right, level+1)
}
}
void visit(TreeNode *root)
{
if (root == NULL)
return;
std::vector<TreeNode*> q,q1;
std::vector<TreeNode*> q1;
std::vector<TreeNode*> *pq = &q;
std::vector<TreeNode*> *pq1 = &q1;
pq->push(root);
while (!pq->empty())
{
printf(pq->at(0)->val);
for (size_t i=0; i<pq->size(); ++i)
{
TreeNode *n = pq->at(i);
if (n->left)
pq1->push_back(n->left);
if (n->right)
pq1->push_back(n->right);
}
pq->clear();
std::swap(pq,pq1);
}
}
void bfs(TreeNode* root)
{
queue< pair<TreeNode*, int> > q;
int pLevel(0), cLevel;
TreeNode* cNode;
if (root != NULL) q.push( make_pair(root, 1) );
while (!q.empty())
{
cNode = q.front().first;
cLevel = q.front().second;
q.pop();
if (cLevel != pLevel) cout << cNode->val << endl;
pLevel = cLevel;
if (cNode->left) q.push( make_pair(cNode->left, cLevel+1) );
if(cNode->right) q.push( make_pair(cNode->right, cLevel+1) );
}
}
public List<T> lefmostAtEachLevel(){
if( isEmpty() ){
return new ArrayList<>();
}
List<T> res = new ArrayList<>();
Queue<NodeLevel<T>> levelQueue = new ArrayDeque<>();
levelQueue.add( new NodeLevel<>(root, 0) );
int prevLevel = -1;
while( ! levelQueue.isEmpty() ){
NodeLevel<T> nodeLevel = levelQueue.poll();
if( nodeLevel.level != prevLevel ){
res.add( nodeLevel.node.value );
prevLevel = nodeLevel.level;
}
for( Node<T> child : nodeLevel.node.children ){
levelQueue.add( new NodeLevel<>(child, nodeLevel.level+1) );
}
}
return res;
}
Do the level order traversal. Print first element after each level change.
int leftMostBinaryTree(struct BinaryTreeNode *root)
{
if(!root) return 0;
struct Queue *Q=CreateQueue();
EnQueue(Q,root);
EnQueue(Q,NULL); //end of first level
while(!IsEmptyQueue(Q)){
root = DeQueue(Q);
if(root == NULL) {
if(!IsEmptyQueue(Q)) //Put another marker for next level
EnQueue(Q,NULL);
if(root->left) //Print left Most element
print("%d",Q->left);
}
else{
if(root->left)
Enqueue(Q,root->left);
if(root->right)
Enqueue(Q,root->right);
}
}
}
your approach is right, but there are potential bug in the code:
if(root == NULL) {
if(!IsEmptyQueue(Q))
EnQueue(Q,NULL);
if(root->left) --> root is null, so will crash it here.
print("%d",Q->left); --> right node can be the leftmost
}
this should be changed to:
if(root == NULL) {
if(!IsEmptyQueue(Q)) {
print front element of the queue
EnQueue(Q,NULL);
}
}
Noticed most of you are assuming a binary tree. The question doesn't state that. My version in javascript:
function Node(val){
this.value = val;
this.children = [];
}
function printLefts(root){
var queue = [];
var node;
var children;
var i;
var previousHeight;
var child;
root.height = 0;
queue.push(root);
while(queue.length > 0){
node = queue.shift();
if(node.height !== previousHeight){
console.log(node.value);
}
children = node.children;
for(i=0;i<children.length;i++){
child = children[i];
child.height = node.height + 1;
queue.push(child);
}
previousHeight = node.height;
}
}
Not my most elegant piece of code. Would love to hear how you would improve this. Linear in number of elements (BF).
void printLeftmostElements(node *root){
std::queue<node *> queue;
queue.push(root);
int current_level = 1, next_level = 0;
std::cout << root->info << " ";
while(!queue.empty()){
node *current = queue.front();
queue.pop();
if (current->left){
++next_level;
queue.push(current->left);
}
if(current->right){
++next_level;
queue.push(current->right);
}
if (--current_level == 0 && next_level > 0){
std::cout << queue.front()->info << " ";
current_level = next_level;
next_level = 0;
}
}
}
void BFS() {
int i, j, k;
q.push_back(1), r.push_back(1);
done[1] = true;
niv[1] = 1;
for (i = 0; i < q.size(); i++) {
k = q[i];
for (j = 0; j < L[k].size(); j++) {
q.push_back( L[k][j] );
niv[ L[k][j] ] = niv[k] + 1;
if (!done[ niv[ L[k][j] ] ]) r.push_back(L[k][j]);
done[ niv[ L[k][j] ] ] = true;
}
}
for (i = 0; i < r.size(); i++)
printf("%d ", r[i]);
}
void LeftMost_Levelwise(struct bst *b, int level) // level=0 at the time of invocation
{
if(b)
{
if(b->lc!=NULL)
printf("Level:\t%d Value:\t%d\n",level,b->lc->data);
LeftMost_Levelwise(b->lc,level+1);
LeftMost_Levelwise(b->rc,level+1);
}
}
You are basically doing an inorder-traversal of the tree, subject to the constraint that only values that belong to the left-most node of each sub-tree are printed.
Wrong solution.
example:
A tree with 2 nodes in which the child is a right node of the root.
The given code will not print any node for that level.
I may not get this example right, but your example has no left node to be printed. Please correct me if I am wrong.
void printLeft(tree * root)
{
static int level = -1;
level++;
if (root == NULL)
{
printf("\nAtLevel: %d, Key:%d", level, root ? root->key : 0);
}
if (root->left)
{
printLeft(root->left);
}
else printLeft(root->right);
}
also your code has many bugs
you are printing only when root==NULL
so,root?root->key?0 will always return 0
it should be if(root==NULL)return;
then the given printf statement
Apart from doing BFS you can use recursion also. The main idea is to remember the level visited for the first time so the you dont print the nodes of the same level when you visit them later.
- Anirban August 02, 2013