Amazon Interview Question
Country: India
Copy all the elements into array O(n) space O(n) time
Sort the array O(nlogn) time
make a doubly linked list O(n) time
Complexity upper bound: O(n)space O(nlogn) time
If the tree were binary search tree then there exist algorithm to convert the same tree in to sorted doubly linked list
thealgorithmist.com/showthread.php/476-BinaryTreeTemplate-All-BST-problems?p=2257&viewfull=1#post2257
- sankarmail February 05, 2012