Amazon Interview Question
Country: India
public TreeNode asDoublyLinkedList(TreeNode root){
if(root.leftChild == null && root.rightChild == null){
return root;
}
else {
TreeNode tmp = null;
tmp = asDoublyLinkedList(root.leftChild);
while(tmp.rightChild != null)
tmp = tmp.rightChild;
tmp.rightChild = root;
root.leftChild = tmp;
tmp = asDoublyLinkedList(root.rightChild);
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 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?
public static DoublyLinkedList<E> returnSortedDoublyLinkedListFromBST(TreeNode rootNode){
if(rootNode != null){
returnSortedDoublyLinkedListFromBST(rootNode.left);
doublyLinkedList.insertLast(new E(rootNode.data));
returnSortedDoublyLinkedListFromBST(rootNode.right);
}
return doublyLinkedList;
}
Now the insertLast method in DoublyLinked List is
public void insertLast(E data){
this.addBefore(tail, data);
}
private void addBefore(DoublyLinkedListNode<E> referenceNode, E data){
DoublyLinkedListNode<E> previous = this.getPreviousNode(referenceNode);
DoublyLinkedListNode<E> next = referenceNode;
DoublyLinkedListNode<E> newNode = new DoublyLinkedListNode<E>(previous,next,data);
next.setPrevious(newNode);
previous.setNext(newNode);
size ++;
}
Another recursive method... use inorder traversal
BST2DLL(node *root, List ** head,List **tail)
{
if(!root)
return Null;
//convert left subtree
BST2DLL(root->left,&head,&tail);
//add the root node to the list
if(!*last) // if this is the left most node
{
*head=root;
*last=*head;
}
else
{
*tail -> right=root;
root->left=*tail;
*tail=root;
}
BST2DLL(root->right,&head,&tail);
}
A recursive solution can be found
int BST2DLL(node** root)
{
stack<node*> s;
node* p = *root;
while(p -> lchild)
{
s.push(p);
p = p -> lchild;
}
//dummy head;
node* head = (node*)malloc(sizeof(node));
if (!head) return 0;
head -> lchild = head;
head -> rchild = head;
node* tail = head;
while(!IsEmpty(s))
{
node* tp = pop(s);
// link
tail -> rchild = tp;
tp -> lchild = tail;
tail = tp;
if(tp - > rchild)
{
node* ttp = tp -> rchild;
while(ttp)
{
push(ttp);
ttp = ttp->lchild;
}
}
}
tail -> rchild = head;
head -> lchild = tail;
return 1;
}
private static void inorder(BSTNode node) {
if (node.getLeft() != null)
inorder(node.getLeft());
//System.out.println(node.getData());
sortedList.add(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());
}
void treetodoublelist(struct node *root, struct node **head, struct node **tail) {
struct node *temp = NULL;
if(root != NULL) {
treetodoublelist(root->left,head,tail);
if(*head == NULL && *tail == NULL) {
*head = (struct node *)malloc(sizeof(struct node));
(*head)->left = NULL;
(*head)->right = NULL;
(*head)->data = root->data;
*tail = *head;
}
else {
temp = (struct node *)malloc(sizeof(struct node));
temp->left = (*tail);
temp->right = NULL;
temp->data = root->data;
(*tail)->right = temp;
*tail = temp;
}
treetodoublelist(root->right,head,tail);
}
}
void treetodoublelist(struct node *root, struct node **head, struct node **tail) {
struct node *temp = NULL;
if(root != NULL) {
treetodoublelist(root->left,head,tail);
if(*head == NULL && *tail == NULL) {
*head = (struct node *)malloc(sizeof(struct node));
(*head)->left = NULL;
(*head)->right = NULL;
(*head)->data = root->data;
*tail = *head;
}
else {
temp = (struct node *)malloc(sizeof(struct node));
temp->left = (*tail);
temp->right = NULL;
temp->data = root->data;
(*tail)->right = temp;
*tail = temp;
}
treetodoublelist(root->right,head,tail);
}
}
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;
}
- Anonymous April 08, 2012