CareerCup

This is one of the recursion problems:

cslibrary. stanford. edu/109/TreeListRecursion. html

start with the left most leaf, keep looking for successor...

//Let T be the root node of bst tree.

main(){
start=createNew(-Infinity);
end=createNew(+Infinity);
start->prev=null;
start->next=end;
end->next=null;
end->prev=start;
bstToLLRight(T,start);
}

bstToLLRight(T,L){
if(T!=null){
node=createNew(T.value);
node->prev=L;
node->next=L->next;
L->next->prev=node;
L->next=node;
bstToLLLeft(T->left,node);
bstToLLRight(T->right,node);
}
}

bstToLLLeftt(T,L){
if(T!=null){
node=createNew(T.value);
node->next=L;
node->prev=L->prev;
L->prev->next = node;
L->prev = node;
bstToLLLeft(T->left,node);
bstToLLRight(T->right,node);
}
}

O(n)
s, s1,s2: struct structure
n: tree node
n->l = node left
n->r = node right

struct
{
	node* max
	node* min
}

INL(n)
	if(n->l == NULL && n->r == NULL)
		return true
	else
		return false
		
TL(n, d)
	if(n == NULL)
		s->max = NULL
		s->min = NULL
		return s
	if(INL(n))
		s->max = n
		s->min = n
		return s
	s1 = TL(n->l)
	s2 = TL(n->r)
	mx1 = s1->max
	mn1 = s1->min
	mx2 = s2->max
	mn2 = s2->min
	n->l = mx1
	mx1->r = n
	n->r = mn2
	mn2->l = n
	s->max = mx2
	s->min = mn1
	return s

void developdlinklistinspace(node1 p)
{
if(p!=null)
{

developdlinklistinspace(p.left);
cratelinkedlist(p);
developdlinklistinspace(p.right);
}
}
node1 head=null,nextnode=null;
node1 cratelinkedlist(node1 p)
{
node1 q=head;
if(head==null)
{
head=p;
nextnode=p;
}
else
{
nextnode.right=p;
nextnode=nextnode.right;
}
return head;
}
void showList()
{
node1 p =head;
while(p!=null)
{
System.out.print(p.val+" ");
p=p.right;
}
}

bst2dbl(root)
  preroot = bst2dbl(root.left)
  p = preroot
  if p != null:
    q = p.right
    while q != null:
      p = q
      q = p.right
  root.left = p
  postroot = bst2dbl(root.right)
  p = postroot
  if p != null:
    q = p.left
    while q != null
      p = q
      q = p.left
  root.right = p
  return root

i have tried to solve this problem by using immediate in-order successor problem. here i have created parent pointer to get parent in O(1) time. but it is not mandatory to have parent pointer. you can get the parent of a node in O(log n) time. please check out the code. you don't need to constrict a tree or write main function. they are already written.

import java.util.ArrayList;



public class tree_to_dubly_linked_list {

	public static class node{
		public int value;
		public node left;
		public node right;
		public node sibl;
		public node sibr;
		public node par;
		
		public node(int v){
			value = v;
			left = null;
			right = null;
			sibl = null;
			sibr = null;
			par = null;
		}
	}
	
	public static class tree{
		public static node root;
		public ArrayList<node> x = new ArrayList<node>();
		
		public tree(){
			root = null;
		}
		
		
		
		
		public void insert(int val){
			root = Insert(root,val);
		}
		
		public node Insert(node n, int val){
			if(n == null){
				node temp = new node(val);
				n = temp;
			}
			else{
				if(val <= n.value){
					n.left = Insert(n.left,val);
					n.left.par = n;
				}
				else{
					n.right = Insert(n.right, val);
					n.right.par = n;
				}
			}
			return n;
		}
		
		public void inorder(){
			inorder(root);
		}
		public void inorder(node n){
			if(n != null){
				inorder(n.left);
				if(n.par == null){
					System.out.print(n.value+"-"+"par: null"+"   ");
				}
				else{
					System.out.print(n.value+"-"+"par:"+n.par.value+"   ");
				}
				inorder(n.right);
			}
		}
		
		public node insuc(int val){
			node t = root;
			while (t != null){
				if(t.value == val){
					return insuc(t);
				}
				else if(val < t.value){
					t = t.left;
				}
				else{
					t = t.right;
				}
			}
			return null;
		}
		public node insuc(node n){
			if(n.par == null || n.right != null){
				return leftmost(n.right);
			}
			else{
				node temp = n;
				node temppar = n.par;
				while(temppar != null && temp != temppar.left){
					temp = temppar;
					temppar = temppar.par;
				}
				if(temppar == null){
					return null;
				}
				else{
					return temppar;
				}
			}
		}
		public node leftmost(node n){
			node nt = n;
			node nl = nt.left;
			while(nl != null){
				nt = nl;
				nl = nl.left;
			}
			return nt;
		}
		
		
		public void ttl(node n)
		{
			if(n != null){
				ttl(n.left);
				node temp = insuc(n);
				if(temp == null){
					n.sibr = null;
				}
				else{
					n.sibr = temp;
					temp.sibl = n;
				}
				ttl(n.right);
			}
		}
		public void ttl(){
			node head = leftmost(root);
			ttl(root);
			node n = head;
			while(n != null){
				if(n.sibl == null || n.sibr == null){
					if(n.sibl == null){
						System.out.println("self: "+n.value+"   "+"left: "+null+"  right: "+n.sibr.value);
					}
					else{
						System.out.println("self: "+n.value+"   "+"left: "+n.sibl.value+"  right: "+null);
					}
				}
				else{
					System.out.println("self: "+n.value+"   "+"left: "+n.sibl.value+"  right: "+n.sibr.value);
				}
				n = n.sibr;
			}
		}
	}
	
	public static void main(String [] s){
		tree t = new tree();
		t.insert(9);
		t.insert(5);
		t.insert(4);
		t.insert(7);
		t.insert(11);
		t.insert(10);
		t.insert(13);
		t.insert(12);
		t.insert(14);
		t.inorder();
		node n = t.insuc(14);
		if(n == null){
			System.out.println("\n"+null);
		}
		t.ttl();
	}
}

BST is already sorted. Traverse your tree in pre-order and add to your doubly linked list