Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
This is basically an application of BFS. We will keep 2 queues- one representing one level and the other representing another.
We start by putting the head in the first queue (Q1). Now, we BFS the head, and add all of its children to Q2 in order. We remove the contents of Q1 and make it a linked list. Now, we BFS Q2 and put all of the children of nodes in Q2 into Q1. Remove the contents of Q2 and make it a linked list. Continue this process of alternating BFS between queues until there are only null values in a queue.
Some Code:
ArrayList linkedListify(Node head) {
Queue q1, q2; //assume these are initialized or whatever
q1.enqueue(head);
ArrayList<LinkedList> ANSWER;
int counter = 0;
while (true) {
LinkedList x = (counter % 2 == 0) ? convertQueueToLinkedList(q1, q2) : convertQueueToLinkedList(q2, q1) ;
if (x == null) { break; }
counter++;
}
return ANSWER;
}
LinkedList convertQueueToLinkedList(Queue q1, Queue q2) {
if (q1.size() == 0) { return null; }
LinkedList list;//initialize
Node current;
Node listToAdd = q1.dequeue();
q2.enqueue(listToAdd.left);
q2.enqueue(listToAdd.right);
current = list.head = listToAdd;
while (q1.size() != 0) {
listToAdd = q1.dequeue();
q2.enqueue(listToAdd.left);
q2.enqueue(listToAdd.right);
current = list.head = listToAdd;
current = current.next;
}
return list;
}
Assuming that it is binary tree
LinkList* createLinkList(Stact<LinkList* >& s)
{
LinkList* head = null;
while(!s.IsEmpty()){
LinkList* tmp = s.pop();
tmp->next = head;
head = tmp;
}
return head;
}
void createLL(TreeNode * node)
{
Queue<TreeNode *> q;
Stact<LinkList* > s;
int tree_enqueue_count = 0;
int tmp_counter = 0;
q.enqueue(node);
tree_enqueue_count++;
while (!q.IsEmpty()){
TreeNode * tmp = q.dequeue();
if (tmp.left != null){
q.enqueue(tmp.left);
tmp_counter++;
}
if (tmp.right != null){
q.enqueue(tmp.right);
tmp_counter++;
}
LinkList * ll = new LinkList();
ll->content = tmp->content;
s.push(ll);
--tree_enqueue_count;
if (tree_enqueue_count == 0){
// Don't know what to do with the head pointer of the linklist. So I just do nothing
createLinkList(&s);
tree_enqueue_count = tmp_counter;
tmp_counter = 0;
}
}
}
void create_list(Node *rootNode)
{
q.push_back(rootNode->left);
q.push_back(rootNode->right);
rootNode->left = NULL;
rootNode->right = NULL;
while(q.size() > 0)
{
q = process_q(q);
}
}
deque<Node*> process_q(deque<Node*> q)
{
deque<Nodes*> qNextLevel;
Node *currentNode = q.front();
q.pop_front();
qNextLevel.push_back(currentNode->left);
qNextLevel.push_back(currentNode->right);
while(q.size() > 0)
{
Node *nextNode = q.front();
qNextLevel.push_back(nextNode->left);
qNextLevel.push_back(nextNode->right);
currentNode->left = NULL;
currentNode->right = nextNode;
currentNode = nextNode;
q.pop_front();
}
currentNode->right = NULL;
return qNextLevel;
}
class ListNode
{
public int Data { get; set; }
public ListNode Next { get; set; }
}
public class TreeNode
{
public int Data { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
}
public static List<ListNode> CreateLevelList(TreeNode root)
{
List<ListNode> result = new List<ListNode>();
if(root == null)
{
return result;
}
Queue<TreeNode> stack = new Queue<TreeNode>();
// Using null as the marker of a new level
queue.Enqueue(root);
queue.Enqueue(null);
ListNode head = new ListNode();
ListNode tail = head;
while(queue.Count > 0)
{
TreeNode node = queue.Dequeue();
if(node == null)
{
result.Add(head);
head = new ListNode();
tail = head;
queue.Enqueue(null);
}
else
{
tail.Next = new ListNode() { Data = node.Data };
tail = tail.Next;
if(node.Left != null)
queue.Enqueue(node.Left);
if(node.Rigth != null)
queue.Enqueue(node.Right);
}
}
return result;
}
#include <iostream>
#include <list>
using namespace std;
class Node {
public:
int val;
Node *left;
Node *right;
Node(int v, Node *l, Node *r) {
val = v;
left = l;
right = r;
}
};
int depth(Node *r) {
if(r==NULL) return 0;
return 1 + max(depth(r->left), depth(r->right));
}
void make_list(Node *r, int cur, int d, list<int>* &l) {
if(r==NULL) return;
if(cur==d) {
l[cur].push_back(r->val);
return;
}
make_list(r->left, cur+1, d, l);
make_list(r->right, cur+1, d, l);
return;
}
void print(list<int>* &l, int d) {
for(int i=0; i<d; i++) {
for(auto it: l[i]) {
cout<<(it)<<" ";
}
cout<<endl;
}
}
int main() {
Node *r = new Node(1, new Node(2, NULL, new Node(4, NULL, NULL)), new Node(3, NULL, new Node(5, NULL, NULL)));
int d = depth(r);
list<int>* l = new list<int>[d]();
for(int i=0; i<d; i++) {
make_list(r, 0, i, l);
}
print(l, d);
return 0;
}
private void connectSameLevelNode1(TreeNode tree){
try{
if(tree == null){
return;
}
if(tree.getLeft() != null){
if(tree.getRight() != null){
tree.getLeft().setNext(tree.getRight());
tree.getRight().setNext(getNextPointer(tree));
}else{
tree.getLeft().setNext(getNextPointer(tree));
}
}else if(tree.getRight() != null){
tree.getRight().setNext(getNextPointer(tree));
}
connectSameLevelNode(tree.getLeft());
connectSameLevelNode(tree.getRight());
}catch(Exception ex){
ex.printStackTrace();
}
}
private TreeNode getNextPointer(TreeNode tree){
try{
TreeNode nextPointer = tree.getNext();
while(nextPointer != null){
if(nextPointer.getLeft()!=null){
return nextPointer.getLeft();
}
if(nextPointer.getRight() != null){
return nextPointer.getRight();
}
nextPointer = nextPointer . getNext();
}
return null;
}catch(Exception ex){
ex.printStackTrace();
}
return null;
}
private void connectSameLevelNode1(TreeNode tree){
try{
if(tree == null){
return;
}
if(tree.getLeft() != null){
if(tree.getRight() != null){
tree.getLeft().setNext(tree.getRight());
tree.getRight().setNext(getNextPointer(tree));
}else{
tree.getLeft().setNext(getNextPointer(tree));
}
}else if(tree.getRight() != null){
tree.getRight().setNext(getNextPointer(tree));
}
connectSameLevelNode(tree.getLeft());
connectSameLevelNode(tree.getRight());
}catch(Exception ex){
ex.printStackTrace();
}
}
private TreeNode getNextPointer(TreeNode tree){
try{
TreeNode nextPointer = tree.getNext();
while(nextPointer != null){
if(nextPointer.getLeft()!=null){
return nextPointer.getLeft();
}
if(nextPointer.getRight() != null){
return nextPointer.getRight();
}
nextPointer = nextPointer . getNext();
}
return null;
}catch(Exception ex){
ex.printStackTrace();
}
return null;
}
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<queue>
struct tree
{
int data;
struct tree * left;
struct tree *right;
};
struct tree * create(int num)
{
struct tree * temp = (struct tree *)malloc(sizeof(struct tree));
temp->data=num;
temp->left=NULL;
temp->right=NULL;
return temp;
}
void insert(struct tree **root,int num)
{
if(*root ==NULL)
{
*root=create(num);
}
else
{
if(num < (*root)->data)
insert(&(*root)->left,num);
else
insert(&(*root)->right,num);
}
}
struct node
{
int data;
struct node *next;
};
struct node * createNode(int num)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
if(temp)
{
temp->data = num;
temp->next = NULL;
return temp;
}
else
return NULL;
}
void addToList(struct node **head, int num)
{
if(*head == NULL)
{
*head = createNode(num);
}
else
{
struct node *temp = *head;
while(temp->next!=NULL)
temp = temp->next;
temp->next = createNode(num);
}
}
void printList(struct node *head)
{
while(head)
{
if(head->next)
printf("%3d->",head->data);
else
printf("%3d",head->data);
head = head->next;
}
}
void freeList(struct node **head)
{
struct node *cur = *head;
struct node *nxt = NULL;
while(cur !=NULL)
{
nxt = cur->next;
free(cur);
cur=nxt;
}
*head = NULL;
}
int MAXM(int a, int b)
{
return a >b ? a : b;
}
int heightOfTree(struct tree *root)
{
if(!root)
return 0;
else
return (1 + MAXM(heightOfTree(root->left), heightOfTree(root->right)));
}
void printEachLevel(struct tree * root, int level, struct node **head)
{
if(root==NULL)
return;
if(level == 1)
{
addToList(head,root->data);
}
else
{
printEachLevel(root->left, level-1,head);
printEachLevel(root->right, level-1,head);
}
}
void printLevelWise(struct tree * root)
{
int height = heightOfTree(root);
struct node *head = NULL;
for(int i = 1; i<=height; i++)
{
printEachLevel(root,i,&head);
printf("\n");
printList(head);
freeList(&head);
}
}
int main()
{
struct tree *root = NULL;
insert(&root,10);
insert(&root,6);
insert(&root,17);
insert(&root,4);
insert(&root,14);
insert(&root,19);
printLevelWise(root);
getch();
return 0;
}
This is just traversing each level and if you encounter the last element in the level, add that corresponding linkedlist to an arrayList. To know if the end of each level has been reached, we can simply add a null in the queue in beginning and if you enounter null while pop, add another.
public static ArrayList<LinkedList<Tree>> linkNodes(Tree root) {
Queue<Tree> queue = new LinkedList<Tree>();
Tree current = root;
if(current != null) {
queue.add(current);
queue.add(null);
}
ArrayList<LinkedList<Tree>> arrayList = new ArrayList<LinkedList<Tree>>();
LinkedList<Tree> list = new LinkedList<Tree>();
while(!queue.isEmpty()) {
current = queue.remove();
list.add(current);
if(current == null) {
arrayList.add(list);
list = new LinkedList<Tree>();
}
else {
if(current.left != null) {
queue.add(current.left);
}
if(current.right != null) {
queue.add(current.right);
}
}
}
return arrayList;
}
sounds about right in your english explanation, except you aren't adding a new null to the end of the queue, so this code will never be able to determine the end of the level after the root level :P
The loop is adding the left and right to the queue only if it is not null, which will reiterate in a recursive fashion to repeat adding non-null lefts and rights, which means you are never adding an extra null.
BFS + create new tree
class ListNode:
def __init__(self,x):
self.val = x
self.next = None
class Solution:
def levelList(self,root):
output = []
outputMid = []
level = [root]
nextLevel = []
while (level):
for item in level:
outputMid.append(item.val)
if item.left:
nextLevel.append(item.left)
if item.right:
nextLevel.append(item.right)
i = 0
level = nextLevel
head = ListNode(output[0])
head1 = head
while (i<=len(outputMid)-2):
item = ListNode(outputMid[i+1])
head1.next = item
i +=1
head1 = head1.next
output.append(head)
return output
#include <iostream>
using namespace std;
struct node{
int data;
struct node *left;
struct node *right;
struct node *nextRight;
}
void connectRightUtil(struct node * root){
if(root==NULL)// if there is Node is NULL
return;
if(root->left==NULL && root->right==NULL){// if there is only one Node
root->nextRight=NULL;
return;
}
connectRight(root);
}
void connectRight(struct node root){
if(root==null)
return;
if(root->left!=NULL){
if(root->right!=NULL){// if right child is not NULL then just put "root->left->nextRight=root->right;"
root->left->nextRight=root->right;
} else{
struct node * result=getRight(root);// get rightmost nextRight Node
if(root->nextRight!=NULL){
root->left->nextRight=right->left? result->left:(result->right?result->right:NULL);
}
else{
root->left->nextRigh=NULL;
}
}
}
if(root->right!=NULL){
root->right->nextRight=right->left? result->left:(result->right?result->right:NULL);
}
connectRight(root->left);
connectRight(root->right);
}
struct node * getRight(struct Node * root){
while(root->left==NULL && root->right==NULL root->nextRight!=NULL)
root=root->nextRight;
return root;
}
Iterative method using Queue:
Aux storage:
Queue traverseQueue
List<LinkedList> or LinkedList[maxLevelOfTree]
int levelIndex
Psuedo code:
traverseQueue.add(root);
levelIndex = 0;
while (traverseQueue.Size() > 0) {
LinkedList head = new LinkedList();
LinkedList current = head;
for (int temp = traverseQueue.size(); temp > 0; temp--) {
TreeNode temp = traverseQueue.remove();
current.value = temp.value;
for (TreeNode child : temp.childs) {
traverseQueue.add(child);
}
if (temp > 1) {
// if not the last node of current level
current.next = new LinkedList();
current = current.next;
}
}
listOfLinkedList[levelIndex] = head;
levelIndex++;
}
return listOfLinkedList;
// MakeTreeToLinkedList.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <memory>
#include <unordered_map>
using namespace std;
struct Node
{
int value;
shared_ptr<Node> left;
shared_ptr<Node> right;
};
struct LinkedListNode
{
int value;
shared_ptr<LinkedListNode> next;
};
struct LinkedList
{
shared_ptr<LinkedListNode> front;
shared_ptr<LinkedListNode> back;
};
void LinkNode(shared_ptr<Node> root, int& currLevel, std::unordered_map<int, shared_ptr<LinkedList>>& linkListNode)
{
if (root == nullptr)
{
return;
}
currLevel++;
LinkNode(root->left, currLevel, linkListNode);
auto tempLLNode = make_shared<LinkedListNode>();
tempLLNode->value = root->value;
tempLLNode->next = nullptr;
auto iter = linkListNode.find(currLevel);
if ( iter == linkListNode.end())
{
// Didn't find the node so add
linkListNode[currLevel] = make_shared<LinkedList>();
linkListNode[currLevel]->front = linkListNode[currLevel]->back = tempLLNode;
}
else
{
linkListNode[currLevel]->back->next = tempLLNode;
linkListNode[currLevel]->back = tempLLNode;
}
LinkNode(root->right, currLevel, linkListNode);
currLevel--;
}
int _tmain(int argc, _TCHAR* argv[])
{
shared_ptr<Node> root = make_shared<Node>();
root->value = 10;
shared_ptr<Node> n6 = make_shared<Node>();
n6->value = 6;
shared_ptr<Node> n17 = make_shared<Node>();
n17->value = 17;
shared_ptr<Node> n4 = make_shared<Node>();
n4->value = 4;
shared_ptr<Node> n14 = make_shared<Node>();
n14->value = 14;
shared_ptr<Node> n19 = make_shared<Node>();
n19->value = 19;
root->left = n6;
root->right = n17;
n6->left = n4;
n17->left = n14;
n17->right = n19;
std::unordered_map<int, shared_ptr<LinkedList>> linkListNode;
int currLevel = -1;
LinkNode(root, currLevel, linkListNode);
for (auto& currMapEntry : linkListNode)
{
printf("\n");
for (auto currNode = currMapEntry.second->front; currNode != nullptr; currNode = currNode->next)
{
printf(" %d", currNode->value);
}
}
return 0;
}
// MakeTreeToLinkedList.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <memory>
#include <unordered_map>
using namespace std;
struct Node
{
int value;
shared_ptr<Node> left;
shared_ptr<Node> right;
};
struct LinkedListNode
{
int value;
shared_ptr<LinkedListNode> next;
};
struct LinkedList
{
shared_ptr<LinkedListNode> front;
shared_ptr<LinkedListNode> back;
};
void LinkNode(shared_ptr<Node> root, int& currLevel, std::unordered_map<int, shared_ptr<LinkedList>>& linkListNode)
{
if (root == nullptr)
{
return;
}
currLevel++;
LinkNode(root->left, currLevel, linkListNode);
auto tempLLNode = make_shared<LinkedListNode>();
tempLLNode->value = root->value;
tempLLNode->next = nullptr;
auto iter = linkListNode.find(currLevel);
if ( iter == linkListNode.end())
{
// Didn't find the node so add
linkListNode[currLevel] = make_shared<LinkedList>();
linkListNode[currLevel]->front = linkListNode[currLevel]->back = tempLLNode;
}
else
{
linkListNode[currLevel]->back->next = tempLLNode;
linkListNode[currLevel]->back = tempLLNode;
}
LinkNode(root->right, currLevel, linkListNode);
currLevel--;
}
int _tmain(int argc, _TCHAR* argv[])
{
shared_ptr<Node> root = make_shared<Node>();
root->value = 10;
shared_ptr<Node> n6 = make_shared<Node>();
n6->value = 6;
shared_ptr<Node> n17 = make_shared<Node>();
n17->value = 17;
shared_ptr<Node> n4 = make_shared<Node>();
n4->value = 4;
shared_ptr<Node> n14 = make_shared<Node>();
n14->value = 14;
shared_ptr<Node> n19 = make_shared<Node>();
n19->value = 19;
root->left = n6;
root->right = n17;
n6->left = n4;
n17->left = n14;
n17->right = n19;
std::unordered_map<int, shared_ptr<LinkedList>> linkListNode;
int currLevel = -1;
LinkNode(root, currLevel, linkListNode);
for (auto& currMapEntry : linkListNode)
{
printf("\n");
for (auto currNode = currMapEntry.second->front; currNode != nullptr; currNode = currNode->next)
{
printf(" %d", currNode->value);
}
}
return 0;
}
// MakeTreeToLinkedList.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <memory>
#include <unordered_map>
using namespace std;
struct Node
{
int value;
shared_ptr<Node> left;
shared_ptr<Node> right;
};
struct LinkedListNode
{
int value;
shared_ptr<LinkedListNode> next;
};
struct LinkedList
{
shared_ptr<LinkedListNode> front;
shared_ptr<LinkedListNode> back;
};
void LinkNode(shared_ptr<Node> root, int& currLevel, std::unordered_map<int, shared_ptr<LinkedList>>& linkListNode)
{
if (root == nullptr)
{
return;
}
currLevel++;
LinkNode(root->left, currLevel, linkListNode);
auto tempLLNode = make_shared<LinkedListNode>();
tempLLNode->value = root->value;
tempLLNode->next = nullptr;
auto iter = linkListNode.find(currLevel);
if ( iter == linkListNode.end())
{
// Didn't find the node so add
linkListNode[currLevel] = make_shared<LinkedList>();
linkListNode[currLevel]->front = linkListNode[currLevel]->back = tempLLNode;
}
else
{
linkListNode[currLevel]->back->next = tempLLNode;
linkListNode[currLevel]->back = tempLLNode;
}
LinkNode(root->right, currLevel, linkListNode);
currLevel--;
}
int _tmain(int argc, _TCHAR* argv[])
{
shared_ptr<Node> root = make_shared<Node>();
root->value = 10;
shared_ptr<Node> n6 = make_shared<Node>();
n6->value = 6;
shared_ptr<Node> n17 = make_shared<Node>();
n17->value = 17;
shared_ptr<Node> n4 = make_shared<Node>();
n4->value = 4;
shared_ptr<Node> n14 = make_shared<Node>();
n14->value = 14;
shared_ptr<Node> n19 = make_shared<Node>();
n19->value = 19;
root->left = n6;
root->right = n17;
n6->left = n4;
n17->left = n14;
n17->right = n19;
std::unordered_map<int, shared_ptr<LinkedList>> linkListNode;
int currLevel = -1;
LinkNode(root, currLevel, linkListNode);
for (auto& currMapEntry : linkListNode)
{
printf("\n");
for (auto currNode = currMapEntry.second->front; currNode != nullptr; currNode = currNode->next)
{
printf(" %d", currNode->value);
}
}
return 0;
}
- GK February 27, 2015