Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Java code:
public static TernaryTreeNode toList(TernaryTreeNode head) {
if (head == null)
return null;
head.left = toList(head.left);
head.middle = toList(head.middle);
head.right = toList(head.right);
TernaryTreeNode newHead;
if (head.left != null) {
head.left = join(head.left, head.middle);
newHead = head.left;
} else {
newHead = head.middle;
}
if (head.middle != null) {
head.middle = join(head.middle, head.right);
} else if(head.left != null) {
head.left = join(head.left, head.right);
} else {
newHead = head.right;
}
if(head.right != null) {
head.right = join(head.right, head);
} else if (head.middle != null) {
head.middle = join(head.middle, head);
} else if (head.left != null) {
head.left = join(head.left, head);
} else {
newHead = head;
}
head.left = null;
return newHead;
}
private static TernaryTreeNode join(TernaryTreeNode node1, TernaryTreeNode node2) {
if (node1 == null) return null;
if(node1.left != null) {
node1.left = join(node1.left, node2);
} else {
node1.left = node2;
}
return node1;
}
public class Ternary {
int data;
Ternary left = new Ternary();
Ternary right = new Ternary();
Ternary child = new Ternary();
public Ternary convert(Ternary root, Ternary tail){
Ternary currNode;
currNode = root;
while(currNode.right!=null){
if(currNode.child!=null){
currNode.child.left = tail;
while(currNode.child.right!=null){
currNode = currNode.right;
}
tail = currNode.right;
}
currNode = currNode.right;
}
return currNode;
}
}
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left,*middle,*right;
};
struct node *newNode(int data)
{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->data=data;
temp->left=temp->middle=temp->right=NULL;
return temp;
}
void ternaryTreetoLL(struct node *root,struct node **prev)
{
if(root==NULL)
return;
ternaryTreetoLL(root->left,prev);
root->left=*prev;
(*prev)=root;
ternaryTreetoLL(root->middle,prev);
ternaryTreetoLL(root->right,prev);
}
void printList(struct node *head)
{
if(head==NULL)
return;
while(head!=NULL)
{
printf("%d ",head->data);
head=head->left;
}
}
int main()
{
struct node *root=newNode(10),*prev=NULL;
root->left=newNode(6);
root->middle=newNode(9);
root->right=newNode(13);
root->left->left=newNode(7);
root->left->middle=newNode(8);
root->left->right=newNode(5);
ternaryTreetoLL(root,&prev);
printList(prev);
getchar();
return 0;
}
Run a BFS and on popping each node from the queue, add it to the linked list. BFS can run either in recursive or explicit queue.
public static TernaryTreeNode toList(TernaryTreeNode head) {
if (head == null)
return null;
head.left = toList(head.left);
head.middle = toList(head.middle);
head.right = toList(head.right);
TernaryTreeNode newHead;
if (head.left != null) {
head.left = join(head.left, head.middle);
newHead = head.left;
} else {
newHead = head.middle;
}
if (head.middle != null) {
head.middle = join(head.middle, head.right);
} else if(head.left != null) {
head.left = join(head.left, head.right);
} else {
newHead = head.right;
}
if(head.right != null) {
head.right = join(head.right, head);
} else if (head.middle != null) {
head.middle = join(head.middle, head);
} else if (head.left != null) {
head.left = join(head.left, head);
} else {
newHead = head;
}
head.left = null;
return newHead;
}
private static TernaryTreeNode join(TernaryTreeNode node1, TernaryTreeNode node2) {
if (node1 == null) return null;
if(node1.left != null) {
node1.left = join(node1.left, node2);
} else {
node1.left = node2;
}
return node1;
}
/*
Might be easier to consider 'left' as the 'next' in the tree and just
move middle and right to left most node while traversing left one at a time.
Algo:
Traverse left and find the left most leaf
current node = root
Till there are no nodes left on the leftside
do this for both middle and right
Add middle to the left most leaf
Add right to the left most leaf
move current one node left
*/
// Adds a given node to the left most
NODE *AddToLeftEnd(NODE *root, NODE *node)
{
while (root->left)
{
root = root->left;
}
root->left = node;
return root;
}
// root becomes 'head' with list linked via 'left' when function returns
void TernaryToList(NODE *root)
{
NODE *end = root, *curr = root;
while (curr)
{
if (curr->middle) {
end = AddToLeftEnd(end, curr->middle);
}
if (curr->right) {
end = AddToLeftEnd(end, curr->right);
}
// Move to next node on left
curr = curr->left;
}
}
Complete running code in java ::
public class TernaryTree2DLL{
// Demonstrate tree->list with the list 1..5
public static void main(String[] args) {
//-------------------------------------------
BTOperation ob=new BTOperation();
TernaryTreeNode r5 = new TernaryTreeNode(5);
TernaryTreeNode r6 = new TernaryTreeNode(6);
TernaryTreeNode r7 = new TernaryTreeNode(7);
TernaryTreeNode r8 = new TernaryTreeNode(8);
TernaryTreeNode r9 = new TernaryTreeNode(9);
TernaryTreeNode r10 = new TernaryTreeNode(10);
TernaryTreeNode r11 = new TernaryTreeNode(11);
TernaryTreeNode r12 = new TernaryTreeNode(12);
TernaryTreeNode r13 = new TernaryTreeNode(13);
TernaryTreeNode r2 = new TernaryTreeNode(2,r5,r6,r7);
TernaryTreeNode r3 = new TernaryTreeNode(3,r8,r9,r10);
TernaryTreeNode r4 = new TernaryTreeNode(4,r11,r12,r13);
TernaryTreeNode root = new TernaryTreeNode(1, r2, r3, r4);
// ob.treeInsert(root,16);
// ob.treeInsert(root,18);
// ob.treeInsert(root,17);
// ob.treeInsert(root,20);
// ob.treeInsert(root,6);
// ob.treeInsert(root,7);
// ob.treeInsert(root,3);
// ob.treeInsert(root,13);
// ob.treeInsert(root,9);
// ob.treeInsert(root,2);
// ob.treeInsert(root,4);
//-------------------------------------------
System.out.println("tree:");
// ob.printTree(root); // 1 2 3 4 5
// System.out.println();
System.out.println("Inorder traversal of tree:");
ob.inOrderTree(root);
TernaryTreeNode head = ob.treeToList(root); // treeToDLL(root);
// TernaryTreeNode head = ob.toList(root);
System.out.println("DLL traversal: ");
ob.printList(head); // 1 2 3 4 5 yay!
}
}
class TernaryTreeNode
{
int data;
TernaryTreeNode left;
TernaryTreeNode middle;
TernaryTreeNode right;
public TernaryTreeNode(int v)
{
this.data=v;
}
public TernaryTreeNode(int v , TernaryTreeNode small, TernaryTreeNode middle , TernaryTreeNode large) {
this.data=v;
this.left = small;
this.middle = middle;
this.right=large;
}
}
class BTOperation {
public TernaryTreeNode treeToList(TernaryTreeNode root)
{
// base case: empty tree -> empty list
if (root==null)
return(null);
// Recursively do the subtrees (leap of faith!)
TernaryTreeNode aList = treeToList(root.left);
TernaryTreeNode bList = treeToList(root.middle);
TernaryTreeNode cList = treeToList(root.right);
// Make the single root node into a list length-1
// in preparation for the appending
root.left = root;
root.right = root;
// At this point we have three lists, and it's
// just a matter of appending them together
// in the right order (aList, root, bList)
aList=append(aList, bList);
aList=append(aList, cList);
aList = append(aList,root );
// root = append(root, bList);
return(aList);
}
public TernaryTreeNode append(TernaryTreeNode a, TernaryTreeNode b)
{
// if either is null, return the other
if (a==null) return(b);
if (b==null) return(a);
// find the last node in each using the .previous pointer
TernaryTreeNode aLast = a.left; // small;
TernaryTreeNode bLast = b.left; // small;
// join the two together to make it connected and circular
join(aLast, b);
join(bLast, a);
return(a);
}
public void join(TernaryTreeNode a, TernaryTreeNode b) {
a.right = b;
b.left = a;
}
/*
Given a non-empty tree, insert a new node in the proper
place. The tree must be non-empty because Java's lack
of reference variables makes that case and this
method messier than they should be.
*/
public void treeInsert(TernaryTreeNode root, int newData) {
if (newData<=root.data)
{
if (root.left!=null)
treeInsert(root.left, newData);
else
root.left = new TernaryTreeNode(newData);
}
else
{
if (root.right!=null)
treeInsert(root.right, newData);
else
root.right = new TernaryTreeNode(newData);
}
}
// Do an inorder traversal to print a tree
// Does not print the ending "\n"
public void printTree(TernaryTreeNode root) {
if (root==null) return;
printTree(root.left);
System.out.print(root.data+ " ");
printTree(root.right);
}
// postorder travseral of tree
public void inOrderTree(TernaryTreeNode root)
{
if(root==null) return;
inOrderTree(root.left);
inOrderTree(root.middle);
inOrderTree(root.right);
System.out.print(root.data+" ");
}
// Do a traversal of the list and print it out
public void printList(TernaryTreeNode head) {
// System.out.println(" head :: " + head.right.right.data);
TernaryTreeNode current = head;
while (true)
{
System.out.print(current.data + " ");
current = current.right;
if(current==head)
{
break;
}
}
System.out.println();
}
}
I think this might work.
- Tushar January 06, 2013