Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
While the actual code is non-intuitive, there is a very easy solution to this problem, if the parent pointer is available at each node:
1. Go to the left most node.
2. Repeatedly call Inorder Successor and before moving to that node, set it as the Right of the current node
In fact, below is the solution in C#, that solves this problem, even if the tree does not have a parent pointer for each node.
This code is going to create a doubly linked list (if the tree is a binary search tree, the resultant linked list will be sorted). It is super easy to modify it to create a singly linked list.
Code in C#:
public class BinarySearchTree
{
public class Node
{
public int data;
public Node left; // In the doubly linked list, this will become previous pointer
public Node right; // And this will become next pointer
}
private Node root; // Root of tree
private Node head; // Head of doubly linked list
private Node prev; // Temporary pointer that stores the previous node, while linked list is being built
public void ToDoublyLinkedList()
{
prev=null;
ToDLL(root);
// If you want to make the doubly linked list circular, uncomment the lines below:
//head.left=prev;
//prev.right=head;
}
private void ToDLL(Node node)
{
if(node==null) return;
ToDLL(node.left);
if(prev!=null) // We are in the middle of inorder traversal.
{
prev.right=node;
node.left=prev; // Comment this line, if you want a singly linked list
}
else // This is the first node in inorder traversal
{
head=node;
head.left=null; // Head should not point back to anything, since this is the first node
node.left=null; // This is already the case, but for the sake of code clarity, I am putting it here
}
// Set current node as prev (why?: imagine the recursive tree for this method. the next node is the inorder successor of this node)
prev=node;
ToDLL(node.right);
}
}
Awesome solution. Nice work. Easily covers, singly, doubly and circular linked list (all cases)!
Flatten( Tree root){
if(root == null)
return null;
else
L = Flatten(root ->left);
R = Flatten(root-right);
root->right = R;
(last Node of L) -> Right = root;
return L;
void inorder(tree t)
{
if(t == NULL)
return;
inorder(t->left);
printf("%d ", t->val);
inorder(t->right);
}
First Add all nodes in a queue in inorder.
Now go through the queue and assign right/left pointers on adjacent elements.
O(n) time
hmm..
tis s my idea. (with one extra static variable pre) give ur suggestions..
do inorder traversal and store the first visiting node in variable pre.
now while visiting each node do the following
pre->right=current; // previous nodes next for first node (i.e pre=NULL) skip tis
current->left=pre; // current nodes previous
pre=current
will this work ???
I wanted to provide a solution that does not require any static variables outside of the recursion loop. That means you have to traverse the nodes to get to the last one before adding the next node, so it is definitely not more efficient than solutions using a static variable, but it is more self-contained.
public BinaryTreeNode FlattenInOrderTree(BinaryTreeNode currentNode)
{
BinaryTreeNode newNode = null;
// Left
if (currentNode.LeftChildNode != null) newNode = FlattenInOrderTree(currentNode.LeftChildNode);
else return new BinaryTreeNode(currentNode.Value);
// Middle
BinaryTreeNode rightMostChildNode = newNode;
while (rightMostChildNode.RightChildNode != null)
rightMostChildNode = rightMostChildNode.RightChildNode;
rightMostChildNode.RightChildNode = new BinaryTreeNode(currentNode.Value);
rightMostChildNode.RightChildNode.ParentNode = rightMostChildNode;
// Right
if (currentNode.RightChildNode != null) rightMostChildNode.RightChildNode.RightChildNode = FlattenInOrderTree(currentNode.RightChildNode);
rightMostChildNode.RightChildNode.RightChildNode.ParentNode = rightMostChildNode.RightChildNode;
return newNode;
}
Node *flatten(Node *root)
{
if (root)
{
root = flatten(root->left);
if (root)
{
add_list(root);
root = flatten(root->right);
}
return NULL;
}
def flatten_util(self,root):
if root:
# if root.left == None and root.right == None:
# return root, root
append = root
x=root.right
if root.left:
left_ll, left_last = self.flatten_util(root.left)
root.right = left_ll
root.left = None
append = left_last
if x:
right_ll, right_last = self.flatten_util(x)
append.right = right_ll
append.left = None
append = right_last
#print_ll(root)
#print
return root, append
This is just a simple question of converting a BST to a linked list (singly or doubly). You can find the answer to this by Googling online
- Anonymous January 13, 2012