|
Convert the BST to sorted doubly linked list , don't use additional data struct.
Microsoft Interview Questions and Answers
(Continued from previous question...)
46. Convert the BST to sorted doubly linked list , don't use additional data struct.
Question:
Convert the BST to sorted doubly linked list , don't use additional data struct.
maybe an answer1:
Basic idea: If we could get a doubly linked list + it's head + it's tail, we could use recursion.
Recursively create list of left subtree, of right subtree and insert the root in the middle, returning the head of left tree and tail of right tree.
Pseudo code...
DLL & TreeToDLL(Tree && t) {
// do base cases, left out.
DLL l = TreeToDLL(t.Left);
DLL r = TreeToDLL(t.Right);
LLNode n = new LLNode(t.value);
return Concat(l, n, r);
}
maybe an answer2:
void join(Node a, Node b) {
a->large = b;
b->small = a;
}
/*
helper function -- given two circular doubly linked
lists, append them and return the new list.
*/
static Node append(Node a, Node b) {
Node aLast, bLast;
if (a==NULL) return(b);
if (b==NULL) return(a);
aLast = a->small;
bLast = b->small;
join(aLast, b);
join(bLast, a);
return(a);
}
/*
--Recursion--
Given an ordered binary tree, recursively change it into
a circular doubly linked list which is returned.
*/
static Node treeToList(Node root) {
Node aList, bList;
if (root==NULL) return(NULL);
/* recursively solve subtrees -- leap of faith! */
aList = treeToList(root->small);
bList = treeToList(root->large);
/* Make a length-1 list ouf of the root */
root->small = root;
root->large = root;
/* Append everything together in sorted order */
aList = append(aList, root);
aList = append(aList, bList);
return(aList);
(Continued on next question...)
Other Interview Questions
| 