Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
public TreeNode[] linkSubTree(TreeNode root) {
TreeNode[] pair = new TreeNode[2];
if (root.left.left == null && root.left.right == null) {
root.left.right = root;
pair[0] = root.left;
} else {
TreeNode[] leftSub = linkSubTree(root.left);
pair[0] = leftSub[0];
root.left = leftSub[1];
leftSub[1].right = root;
}
if (root.right.left == null && root.right.right == null) {
root.right.left = root;
pair[1] = root.right;
} else {
TreeNode[] rightSub = linkSubTree(root.right);
pair[1] = rightSub[1];
root.right = rightSub[0];
rightSub[0].left = root;
}
return pair;
}
struct tree_node
{
int data;
struct node * left;
struct node * right;
};
typedef struct tree_node * ptr_to_node;
ptr_to_node root=NULL;
ptr_to_node head=NULL;
ptr_to_node temp2;
void convertolist(ptr_to_node temp)
{
if(temp->left !=NULL)
convertolist(temp->left);
if(head==NULL)
head=temp2=temp;
else
{
temp2->right=temp;
temp->left=temp2;
temp2=temp;
}
if(temp->right !=NULL)
convertolist(temp->right);
}
TreeNode * ConvertToDoublyLinkedList(TreeNode * root)
{
if(NULL == root)
return NULL;
TreeNode * left = ConvertToDoublyLinkedList(root->left);
// root's left is the rightmost element of the left sub tree
TreeNode * leftTemp = left;
while(leftTemp && leftTemp->right)
leftTemp = leftTemp->right;
root->left = leftTemp;
if(leftTemp)
leftTemp->right = root;
TreeNode * right = ConvertToDoublyLinkedList(root->right);
// root's right is the leftmost element of the right sub tree
TreeNode * rightTemp = right;
while(rightTemp && rightTemp->left)
rightTemp = rightTemp->left;
root->right = rightTemp;
if(rightTemp)
rightTemp->left = root;
return root;
}
The final root points to the actual root in the BST. you can traverse left or right to reach the front or the end of the doubly linked list.
I am using the "left" and "right" members for the "prev" and "next".
.leetcode.com/2010/11/convert-binary-search-tree-bst-to.html
- begineer July 16, 2012