## Akamai Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

how does this work? you are not adding anything to queue1 later in while loop, and in every loop you create a new queue2 ? i doubt this code works

Yea, its my BAD i forgot to assign it back to level1, thanks for the correction:

```
Algorithm:
==========
Queue level1 = new Queue();
level1.add(rootNode);
Node lastNode = null;
while(!level1.isEmpty()){
Queue level2 = new Queue();
while(!level1.isEmpty()){
Node currentParent = queue.dequeue();
if(currentParent.hasLeftNode()){
Node leftChild = currentParent.leftNode();
if(lastNode != null){
lastNode.next() = leftChild;
}
lastNode = leftChild;
level2.add(leftChild);
}
if(currentParent.hasRightNode()){
Node rightChild = currentParent.rightNode();
if(lastNode != null){
lastNode.next() = rightChild;
}
lastNode = rightChild;
level2.add(rightChild);
}
}
level1 = level2;
}
```

Space O(L) where L = number of nodes at one level, Time O(N)

Is the next pointer supposed to point to the node on the same level? If yes what happens if there are no nodes on the right at a give level.

I have attempted a possible solution, but may still needs to be refined/corrected

```
change_tree(struct node *root)
{
if (root == NULL)
return;
root->next = NULL;
if (root->left)
root->left->next = root->right;
if (root->right)
root->right->next = NULL;
if (root->left){
assign_next_from_parent(root->left->left,root->left);
assign_next_from_parent(root->left->right,root->left);
}
if (root->right) {
assign_next_from_parent(root->right->left,root->left);
assign_next_from_parent(root->right->right,root->left);
}
assign_next_from_parent(struct node *node, struct node *parent)
{
if(parent->right)
node->next = parent->right;
elseif (parent->next) {
if (parent->next->left)node->next = parent->next->left;
else node->next = parent->next->right;
} else {
node->next = NULL;
}
assign_next_from_parent(node->left,node);
assign_next_from_parent(node->right, node);
}
```

I have a solution O(1) space and O(n) time, where n - number of nodes.

```
void connect(TreeLinkNode *root) {
if(!root) return;
TreeLinkNode * cur = root;
root -> next = NULL;
while( cur -> left ){
TreeLinkNode * connect = cur;
while (connect -> next){
connect -> left -> next = connect -> right;
connect -> right -> next = connect -> next -> left;
connect = connect -> next;
}
cur = cur -> left;
connect -> left -> next = connect -> right;
connect -> right -> next = NULL;
}
```

```
#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode* thePtr;
TreeNode(int data) : data(data), left(NULL), right(NULL) {}
TreeNode(int data, TreeNode* left, TreeNode* right) : data(data), left(left), right(right) {}
};
void addLinks(TreeNode* root) {
if (!root) return;
queue<TreeNode*> nq;
nq.push(root);
nq.push(NULL);
TreeNode* prev = NULL;
while (!nq.empty()) {
TreeNode *t = nq.front();
nq.pop();
if (prev)
prev->thePtr = t;
prev = t;
if (t && t->left)
nq.push(t->left);
if (t && t->right)
nq.push(t->right);
if (!t && !nq.empty())
nq.push(t);
}
}
TreeNode* makeNode(int data, TreeNode *left = NULL, TreeNode *right = NULL) {
return new TreeNode(data, left, right);
}
void printLinks(TreeNode *root) {
TreeNode* t = root;
while (t) {
cout << t->data << ": ";
TreeNode* tptr = t;
while (tptr) {
cout << tptr->data << " ";
tptr = tptr->thePtr;
}
cout << endl;
t = t->left;
}
}
void test_addLinks() {
TreeNode *root = makeNode(10);
root->left = makeNode(12);
root->right = makeNode(15);
root->left->left = makeNode(8, makeNode(9), makeNode(4));
root->left->right = makeNode(14, NULL, makeNode(7));
root->right->left = makeNode(45, makeNode(2), makeNode(11));
root->right->right = makeNode(26, NULL, makeNode(12));
addLinks(root);
printLinks(root);
}
int main() {
test_addLinks();
cin.ignore();
}
```

No assumption seems to be made about the the data structure of the binary tree. If its implemented as an array, then finding nodes to the right boils down to a matter of just examining the index.

```
#include <vector>
struct node
{
unsigned data;
bool is_null;
node *right;
}
void connect_right(vector<node> tree)
{
for(int i = 0; i < tree.size; i++)
{
if(!tree[i].is_null)
{
for(int j = i + 1; (j & (j + 1)) == 0; j++)
{
if(!tree[j].is_null)
{
tree[i].right = tree + j;
}
}
}
}
}
```

- Ajeet July 14, 2014