## Adobe Interview Question

Software Engineer / Developers**Country:**India

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.

// 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);

}

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> head = null;

TreeNode<int> last = null;

FlatBst(bst.Root,ref last,ref head);

TreeNode<int> node = head;

while (node != null)

{

Console.Write(node.Element);

Console.Write(" ");

node = node.Right;

}

Console.Read();

}

static void FlatBst(TreeNode<int> node,ref TreeNode<int> prev,ref TreeNode<int> head)

{

if (node != null)

{

FlatBst(node.Left,ref prev,ref head);

node.Left = prev;

if (prev== null)

{

head = node;

}

else

prev.Right = node;

prev = node;

FlatBst(node.Right,ref prev,ref head);

}

}

```
struct node *linearizeR(struct node *currHead){
if(currHead->right == NULL && currHead->left == NULL)
return currHead;
if(currHead->right == NULL){
currHead->left = linearizeL(currHead->left);
currHead->left->right = currHead;
currHead->left->left = findParent(currHead);
return currHead->left;
}
if(currHead->left == NULL){
currHead->right = linearizeR(currHead->right);
return currHead;
}
//linearize right tree and return left
currHead->right = linearizeR(currHead->right);
currHead->left = linearizeL(currHead->left);
currHead->left->right = currHead;
currHead->left->left = findParent(currHead);
return currHead->left;
}
struct node *linearizeL(struct node *currHead){
if(currHead->right == NULL && currHead->left == NULL)
return currHead;
if(currHead->right == NULL){
currHead->left = linearizeL(currHead->left);
return currHead;
}
if(currHead->left == NULL){
currHead->right = linearizeR(currHead->right);
currHead->right->left = currHead;
currHead->right->right = findParent(currHead);
return currHead->right;
}
//linearize right tree and return left
currHead->right = linearizeR(currHead->right);
currHead->left = linearizeL(currHead->left);
//make sure the right ka left points to currHead and right ka right points to currHead->parent!
currHead->right->left = currHead;
currHead->right->right = findParent(currHead);
return currHead->right;
}
the above two functions linearize the tree to doubly linked list..recursively...
```

```
static TreeJ prev1=null;
void binaryTree2DoubleLinkedList(TreeJ root, TreeJ doublyLL)
{
// Base case
if (root == null){
return;
}
// Recursively convert left subtree
binaryTree2DoubleLinkedList(root.left, doublyLL);
// Now convert this node
if (prev1 == null){
doublyLL = root;
}
else {
root.left = prev1;
prev1.right = root;
}
prev1=root;
// Finally convert right subtree
binaryTree2DoubleLinkedList(root.right, doublyLL);
}
```

// 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;

treeToDoublyList(p->left, prev, head);

// 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

head = p; // current node (smallest element) is head of

// 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;

head->left = p;

p->right = head;

// updates previous node

prev = p;

treeToDoublyList(right, prev, head);

}

// 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;

Node *head = NULL;

treeToDoublyList(root, prev, head);

return head;

}

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*/
node * flattenBST(node* head)
{
node *h=head;
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;
}
h=head;
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;
}
```

```
int bst2dll(struct node* root, struct node** head ){
queue<struct node* > Q;
Q.push(root);
*head = 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

youtube.com/watch?v=WJZtqZJpSlQ

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.

- Arun August 27, 2012