convert binary tree to double linked list

Question

Anonymous · Accepted Answer

I'm going through that process right now. Hopefully in between the phone screens and onsite interview but I may well just be at the end of the road with Amazon. I'll find out I suppose. I didn't get anything close to this question though. But here's my shot.

If you need to use the same nodes and keep them in order, you might consider right and left to be prev and next and make the binary search tree no longer a binary search tree and instead a doubly linked list.

std::pair flatten_and_return_ends(node *root_node)
{
    node *first, *last;
    if (root_node->left)
    {
        std::pair left_minmax = flatten_and_return_ends(root_node->left);
        first = left_minmax.first;
        left_minmax.second->right = root_node;
        root_node->left = left_minmax.second;
    }
    else
        first = root_node;
    
    if (root_node->right)
    {
        std::pair right_minmax = flatten_and_return_ends(root_node->right);
        root_node->right = right_minmax.first;
        right_minmax.first->left = root_node;
        last = right_minmax.second;
    }
    else
        last = root_node;
    
    return std::pair(first, last);
}

on the other hand, if they just want you to push the nodes in order into a list

template
void add_to_list(node *root_node, list &values)
{
    if (root_node->left)
        add_to_list(root_node->left, values);
    values.push_back(root_node->value);
    if (root_node->right)
        add_to_list(root_node->right, values);
}

I didn't check for validity so there may be typos

Gaurav Agarwal · Answer

Check out this in place DoublyLinked Conversion of Tree.
1.  Link a Node to its leftchild's rightchild as its leftchild.
2.  Make Node as right child of original leftchild.
3.  Apply recursion.  

Node fn = null ;                    //First Node
Node ln = null ;                   // Last Node

public Node asDoublyLinkedList(Node root){                      
		
		Node parent = root;
		Node current = root.leftNode;
		
		while(true){
		if(current==null) {
			if(fn==null) fn = parent;
			if(parent.rightNode==null){
				ln = parent;
				return parent;
			}
			Node n = asDoublyLinkedList(parent.rightNode);
			parent.rightNode = n;
			n.leftNode = parent;
			if(ln!=null){
			ln.rightNode = fn;
			fn.leftNode = ln;
			}
			return parent;
		}
		
		parent.leftNode = current.rightNode;
		current.rightNode = parent;
		parent = current;
		current = parent.leftNode;
		}
		
		
		
	}

Rajkumar · Answer

Do inorder traversal
Pass char **root as the second argument to the traversal function along with whatever argument you to pass to the function
As part of processing, instead of displaying the content of the node, store the node in the second argument root, if root is not already NULL. Else store the current node as the right most node by iterating through the linked list where root is the starting node.

Amazon

Amazon interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches