Amazon Interview Question
Software Engineer / DevelopersTeam: RCX
Country: United States
Interview Type: In-Person
This code will create a nextRight link for all left nodes. I am guessing the question is assuming that the right child needs to be connected to the left most child on the level below?
Good point. If that is what you want, we can do a BFS search, push everything on to a stack and then pop one by one and assign pointers. Here is the code in C#:
private void PopulateAllNextRight(Node node)
{
Stack<Node> allNodes=new Stack<Node>();
Queue<Node> bfs=new Queue<Node>();
bfs.Enqueue(node);
while(bfs.Count>0)
{
node=bfs.Dequeue();
allNodes.Push(node);
// Process children
if(node.leftChild!=null) bfs.Enqueue(node.leftChild);
if(node.rightChild!=null) bfs.Enqueue(node.rightChild);
}
if(allNodes.Count>0)
{
Node temp=allNodes.Pop();
while(allNodes.Count>0)
{
node=allNodes.Pop();
node.nextRight=temp;
temp=node;
}
}
}
Consider this Binary Tree;
1
2 3
4 5 6 7
We can observe that for a given r, r.left, and r.right. then a) r.left.nextR = r.right.left and b) r.right.nextR = r.nextR.left. So if we traverse the tree in preOrder we can effectively propagate the nextR, hence;
void propagate(Node r){ //begin with r = root
if(r.left != null){
if(r.right != null) r.left.nextR = r.right.left;
propagate(r.left);
}
if(r.right != null) {
if(r.nextR != null) r.right.nextR = r.nextR.left;
propagate(r.right);
}
}//end
void SetNextRightNode(node* root)
{
if(root)
{
node* dummy = new node(100000);
if(!dummy)
return;
queue<node*,100> q;
q.enqueue(root);
q.enqueue(dummy);
while(q.isEmpty() == false)
{
node* cur = NULL;
node* prev = NULL;
while((cur = q.dequeue()) != dummy)
{
if(cur->left)
q.enqueue(cur->left);
if(cur->right)
q.enqueue(cur->right);
if(prev)
{
prev->nextRight = cur;
}
prev = cur;
}
q.enqueue(dummy);
}
delete dummy;
}
}
void SetNextRightNode(node* root)
{
if(root)
{
node* dummy = new node(100000);
if(!dummy)
return;
queue<node*,100> q;
q.enqueue(root);
q.enqueue(dummy);
while(q.isEmpty() == false)
{
node* cur = NULL;
node* prev = NULL;
while((cur = q.dequeue()) != dummy)
{
if(cur->left)
q.enqueue(cur->left);
if(cur->right)
q.enqueue(cur->right);
if(prev)
{
prev->nextRight = cur;
}
prev = cur;
}
q.enqueue(dummy);
}
delete dummy;
}
}
We can do this with a single depth first traversal and O(log(n)) space. Important thing is to traverse the right subtrees before the left subtrees. For each level of the tree, we keep a pointer to the last visited node in that level of the tree. In the helper function, we just set the rightChild of the current node to the corresponding element in the array and update the element in the array to be the current node so that next time we are visiting a node in that level, we set the rightChild of that node to the correct Node.
void populate(Node* n) {
vector<Node*> R;
populateHelper(n, R, 0);
}
void populateHelper(Node* n, vector<Node*> & R, int h) {
if ( n == NULL ) return; // obvious
// if we are at this level for the first time, initialize the
// corresponding element of R with NULL
if ( h == R.size() ) R.push_back(NULL);
n->rightChild = R[h]; // get last visited Node in that level from R
R[h++] = n; // update R and increment h
populateHelper(n->rightChild, R, h); // traverse right subtree first
populateHelper(n->leftChild, R, h);
}
void SetSibling(treenode* root)
{
if(root == NULL)
return;
else
{
// Set the siblings
treenode* candidate = NULL;
if(root->left == NULL)
{
if(root->right == NULL)
candidate = NULL;
else
candidate = root->right;
}
else
{
if(root->right == NULL)
candidate = root->left;
else
{
root->left->sibling = root->right;
candidate = root->right;
}
}
treenode* ptr = root->sibling;
treenode* result = NULL;
if(candidate)
{
while(ptr!=NULL)
{
if(ptr->left != NULL)
{
result = ptr->left;
break;
}
else if(ptr->right != NULL)
{
result = ptr->right;
break;
}
ptr = ptr->sibling;
}
candidate->sibling = result;
}
SetSibling(root->right);
SetSibling(root->left);
}
}
C#:
- Anonymous January 06, 2012