Amazon Interview Question
Software Engineer / DevelopersCountry: India
@svsujeet ya that is what i also think,but interview told me ans like using recursion . even i told him many other soln.
Modified version(not a circular linked list) of the link above
class Node{
int value = 0;
Node left = null;
Node right = null;
Node(int value) {
this.value = value;
}
}
public class TreeToList{
public Node treeToList(Node n) {
if (n == null) return null;
Node aList = treeToList(n.left);
Node bList = treeToList(n.right);
if (aList == null && bList == null) {
return n;
} else {
if (aList != null) {
Node aListLast = aList;
while (aListLast != null && aListLast.right != null) {
aListLast = aListLast.right;
}
aListLast.right = n;
n.left = aListLast;
} if (bList != null) {
n.right = bList;
bList.left = n;
}
}
return aList;
}
public Node createTree() {
Node _1 = new Node(1);
Node _2 = new Node(2);
Node _3 = new Node(3);
Node _4 = new Node(4);
Node _5 = new Node(5);
Node _6 = new Node(6);
Node _7 = new Node(7);
_4.left = _2;
_4.right = _6;
_2.left= _1;
_2.right = _3;
_6.left = _5;
_6.right = _7;
return _4;
}
public void printLinkedList(Node n) {
while (n != null) {
System.out.print (n.value);
if (n.right != null) {
System.out.print (" --> ");
}
n = n.right;
}
System.out.println();
}
public static void main (String [] args) {
TreeToList ttl = new TreeToList();
Node root = ttl.createTree();
Node head = ttl.treeToList(root);
ttl.printLinkedList(head);
}
}
//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;
}
}
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
you can't use extra space for doubly link list .. you have only o(1) memory. and had to manipulate within BST.
Also, should we not traverse the tree in-order(instead of pre-order) for getting your sorted list?
This is one of the recursion problems:
- hello world February 03, 2012cslibrary. stanford. edu/109/TreeListRecursion. html