## Adobe Interview Question for Software Engineer / Developers

Country: India

Comment hidden because of low score. Click to expand.
0
of 0 vote

If a node has right child, append it to the leftmost child ( keep on follow the left child of the nodes, until you reach a node whose left child is null). conver the link between the node and its child to a doubly linked list. Now start the algorithm again from the left child. Repeat the algorithm until no node has right child.

Comment hidden because of low score. Click to expand.
0

forgot the extra space constraint My Bad !!

Comment hidden because of low score. Click to expand.
0

There is no extra space required for this algorithm. This Algorithm should run faster than the other algorithm.

for example if you are given a tree
1
/ \
2 3
\
4

the Algorithm will start by taking 3 and adding it to the 2
1
/
2
/ \
3 4

Then by
1
/
2
/
3
/
4

At this point it can be converted to doubly linked list, since no node has right child.

Comment hidden because of low score. Click to expand.
0

On Reading the other solution, they are exactly the one and the same. The run time will not be o(n^2) as you can remember the left most point, that you are in now and every node needs to be visited only once. So it will be O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

can't we use a queue for this purpose ??

Comment hidden because of low score. Click to expand.
0

Queue would be best suited for this problem.

Comment hidden because of low score. Click to expand.
0
of 0 vote

// tree element
struct TreeEl
{
TreeEl* left;
TreeEl* right;
int data;
};

void TreeToList(TreeEl* curEl) // give root of tree
{
if (curEl->left)
TreeToList(curEl->left);

static TreeEl* prevEl = NULL;

if (prevEl)
{
prevEl->right = curEl;
curEl->left = prevEl;
}

prevEl = curEl;

if (curEl->right)
TreeToList(curEl->right);
}

Comment hidden because of low score. Click to expand.
0

its simple and good:)

Comment hidden because of low score. Click to expand.
0

why??
static TreeEl* prevEl = NULL;
in recursion

Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
{
BinarySearchTree<int> bst = new BinarySearchTree<int>();
int[] arr = { 15, 6, 18, 3, 7, 17, 20, 2, 4, 13,9 };
for (int i = 0; i < arr.Length; i++)
{
bst.Insert(arr[i]);
}
TreeNode<int> last = null;
while (node != null)
{
Console.Write(node.Element);
Console.Write(" ");
node = node.Right;
}
}

static void FlatBst(TreeNode<int> node,ref TreeNode<int> prev,ref TreeNode<int> head)
{
if (node != null)
{
node.Left = prev;
if (prev== null)
{
}
else
prev.Right = node;
prev = node;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````struct node *linearizeR(struct node *currHead){

}
}

//linearize right tree and return left

}

}
}

//linearize right tree and return left

//make sure the right ka left points to currHead and right ka right points to currHead->parent!

}

the above two functions linearize the tree to doubly linked list..recursively...``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

not using extra memory means no extra memory for any new node, it doesnot means u cant use Queue for this.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static TreeJ prev1=null;
{
// Base case
if (root == null){
return;
}

// Recursively convert left subtree

// Now convert this node
if (prev1 == null){
doublyLL = root;
}
else {
root.left = prev1;
prev1.right = root;
}
prev1=root;

// Finally convert right subtree
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

// This is a modified in-order traversal adapted to this problem.
// prev (init to NULL) is used to keep track of previously traversed node.
// head pointer is updated with the list's head as recursion ends.
void treeToDoublyList(Node *p, Node *& prev, Node *& head) {
if (!p) return;
// current node's left points to previous node
p->left = prev;
if (prev)
prev->right = p; // previous node's right points to current node
else
// the list if previous node is not available
// as soon as the recursion ends, the head's left pointer
// points to the last node, and the last node's right pointer
// points to the head pointer.
Node *right = p->right;
prev = p;
}

// Given an ordered binary tree, returns a sorted circular
// doubly-linked list. The conversion is done in-place.
Node* treeToDoublyList(Node *root) {
Node *prev = NULL;
}

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Hi Naseer Quick sort is inplace or not?

Comment hidden because of low score. Click to expand.
-1
of 13 vote

There is a way to do the job in place.
Start from root,
1- go to the right node, lets say setPoint node,
2- if there is any node in left, move this node to the most right node of setPoint
3- if there is NULL in setPoint->left, point to the setPoint's parent (we are going to make a double link list)
4- continue from step 1 with Setpoint->right until the end of chain

now with the same logic apply the algorithm with root->left

at the end we have a double linked list

here is the code in C

of course the complexity of this method is o(n^2) while for each node is needed to trace all left or right nodes.

Any suggestion? better idea?

``````/* Flatten BST*/
{
while(h->right!=NULL)
{
if(h->right->left!=NULL)
{
node *mostRight, *setPoint;
setPoint=mostRight=h->right;
while(mostRight->right!=NULL)
mostRight=mostRight->right;
mostRight->right=setPoint->left;
setPoint->left=h;
}
else
h->right->left=h;
h=h->right;
}
while(h->left!=NULL)
{
if(h->left->right!=NULL)
{
node *mostLeft, *setPoint;
setPoint=mostLeft=h->left;
while(mostLeft->left!=NULL)
mostLeft=mostLeft->left;
mostLeft->left=setPoint->right;
setPoint->right=h;
}
else
h->left->right=h;
h=h->left;
}
return h;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't see a stack or recursion, so I wonder if this function actually covers the whole tree.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````int bst2dll(struct node* root, struct node** head ){
queue<struct node* > Q;
Q.push(root);

struct node* last= NULL;
struct node* node= NULL;

while ( !Q.empty()){
node = Q.front();
Q.pop();
if(node->left)
Q.push(node->left);

if(node->right)
Q.push(node->right);

node->left = last;
node->right = Q.front();
last = node;
}

}``````

To understand this concept you may watch this video tutorial

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Queue is not using any extra space, it is just storing the bst nodes and then arranging it into queue.

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.