Akamai Interview Question
Software Engineer / DevelopersCountry: 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