## Amazon Interview Question

Country: India

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

``````//Just to inorder travesal with predecessor in mind to link it.

node* treetoDLL(node* root)
{
static node *start,*pred =NULL;
if(root==NULL)
return NULL;

treetoDLL(root->lptr);

node *dnode = new node();
dnode->data =root->data;
dnode->rptr = NULL;
dnode->lptr =pred;

if(pred!=NULL)
pred->rptr =dnode;
else
start = dnode;
pred=dnode;

treetoDLL(root->rptr);
return start;
}``````

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

For left child or right child null it gives null pointer exception

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

``````public TreeNode asDoublyLinkedList(TreeNode root){
if(root.leftChild == null && root.rightChild == null){
return root;
}
else {
TreeNode tmp = null;
while(tmp.rightChild != null)
tmp = tmp.rightChild;
tmp.rightChild = root;
root.leftChild = tmp;
while(tmp.leftChild != null)
tmp = tmp.leftChild;
tmp.leftChild = root;
root.rightChild = tmp;
}

return root;
}``````

This works but the root pointer will still point to the root of the tree. Do a while root = root.leftChild and finally the root shall point to the head of doubly linked list.

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

complexty is n^2. Did the same thing in python

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

Comment from OP:
Tweaked inorder traversal and gave the below answer

``````BST to sorted LL
p = root;
visited = NULL;
do
{
while( p!=NULL )
stack.push(p);
p = p->left;

while( !stack.empty() )
{
temp = stack.pop()
visit(temp);
if( visited != NULL )
visited->right = temp;
temp->left = visited;
visited = temp;
if( temp->right )
p = temp->right;
break;
}
while( p!= NULL || !stack.empty() );``````

You need to an inorder traversal(which takes up O(n) space) to realize the sortedness of the number. Having said that, is there any way to do this in O(1) space?

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

if(rootNode != null){
}
}

Now the insertLast method in DoublyLinked List is

public void insertLast(E data){
}

next.setPrevious(newNode);
previous.setNext(newNode);
size ++;
}

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

Another recursive method... use inorder traversal

BST2DLL(node *root, List ** head,List **tail)
{
if(!root)
return Null;

//convert left subtree

//add the root node to the list

if(!*last) // if this is the left most node
{
}
else
{
*tail -> right=root;
root->left=*tail;
*tail=root;
}

}

A recursive solution can be found

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

this is not a non recursion solution...u have used inorder using recursion... :P :P

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

``````int BST2DLL(node** root)
{
stack<node*> s;
node* p = *root;
while(p -> lchild)
{
s.push(p);
p = p -> lchild;
}

while(!IsEmpty(s))
{
node* tp = pop(s);

tail -> rchild = tp;
tp -> lchild = tail;
tail = tp;

if(tp - > rchild)
{
node* ttp = tp -> rchild;
while(ttp)
{
push(ttp);
ttp = ttp->lchild;
}
}
}

return 1;
}``````

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

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

private static void inorder(BSTNode node) {
if (node.getLeft() != null)
inorder(node.getLeft());
//System.out.println(node.getData());
if (node.getRight() != null)
inorder(node.getRight());
}

private static void traverse() {
ListIterator dll = sortedList.listIterator();

System.out.println("Forward traversing");
while (dll.hasNext())
System.out.println(dll.next());

System.out.println("==============================");
System.out.println("Backward traversing");
while (dll.hasPrevious())
System.out.println(dll.previous());
}

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

Was someone actually trying cross side scripting

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

Was someone actually trying cross side scripting!!!

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

Was someone actually trying cross side scripting!!!

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

void treetodoublelist(struct node *root, struct node **head, struct node **tail) {
struct node *temp = NULL;
if(root != NULL) {
if(*head == NULL && *tail == NULL) {
*head = (struct node *)malloc(sizeof(struct node));
}
else {
temp = (struct node *)malloc(sizeof(struct node));
temp->left = (*tail);
temp->right = NULL;
temp->data = root->data;
(*tail)->right = temp;
*tail = temp;
}
}
}

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

``````void treetodoublelist(struct node *root, struct node **head, struct node **tail) {
struct node *temp = NULL;
if(root != NULL) {
if(*head == NULL && *tail == NULL)  {
*head = (struct node *)malloc(sizeof(struct node));
}
else {
temp = (struct node *)malloc(sizeof(struct node));
temp->left = (*tail);
temp->right = NULL;
temp->data = root->data;
(*tail)->right = temp;
*tail = temp;
}
}
}``````

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

testing

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

``````public TreeNode convert(TreeNode node)
{
if(node== null)
return null;

if(node.leftchild==null && node.rightchild== null)
return node;

else
{	TreeNode temp = null;

temp  = convert(node.leftchild);
if(temp!=null)
{
while(temp.rightchild!=null)
temp= temp.rightchild;
temp.rightchild = node;
node.leftchild = temp;
}
temp = convert(node.rightchild);
if(temp!=null)
{
while(temp.leftchild!=null)
temp = temp.leftchild;
temp.leftchild = node;
node.rightchild = temp;
}
}
return node;

}``````

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.