Microsoft Interview Question
Software Engineer in Tests@smritedua - Its for a Nary tree, not binary
Tnode MirrorTree(TNode tnode)
{
// Don't do anything if the number of children is less than one
if(tnode.Children.Count < 2) return tnode;
// else push the children into a stack and set that as children
List<TNode> children = tnode.Children;
List<TNode> stack = new List<TNode>;
foreach(TNode t in children){
stack.insertAt(0,MirrorTree(t));
}
t.Children = stack;
children = null;
return tnode;
}
This is just postorder traversal but except that we swap the child nodes instead of printing the parent's value. Guess seeker7's code works fine.
though seeker7 code is for a binary tree , but it can be extedended for to work for n-ry tree
use the same logic as in post1
mirror(*root->first);
mirror(*root->secord);
.
.
.
mirror(root->nth);
swap(root->first, root->nth);
swap(root->second, root->(n-1)th);
.
.
.
swap(root->(n/2)th, root->(n/2+1)th);
static void mirrorImageOfntree<T>(nNode<T> head)
{
if (head == null) return;
int i = 0;
int j = head.Children.Length - 1;
while (i < j)
{
nNode<T> temp;
temp = head.Children[i];
head.Children[i] = head.Children[j];
head.Children[j] = temp;
i++;
j--;
}
foreach (nNode<T> node in head.Children)
{
mirrorImageOfntree<T>(node);
}
}
//class that represents a node in n-Tree
class nNode<T>
{
public nNode(int children, T value)
{
this.children = new nNode<T>[children];
this.value = value;
}
nNode<T>[] children;
T value;
public nNode<T>[] Children
{
get{return children;}
}
public nNode<T> this[int index]
{
get{ return this.children[index];}
set{children[index] = value;}
}
}
typedef struct nodeT
{
node* child[MAX];
int data;
}node;
void mirroImageNaryTree(node* root)
{
if(root == null)
while(int i=0; i< max; i++)
{
if(root->child[i] == null)
continue;
if(root->child[i] != null)
mirroImageNaryTree(root->child[i]);
}
reverseChildren[root->child];
}
void reverseChildren(node* child[])
{
start = 0;
end = MAX;
while(start < end)
{
node* temp = child[start];
child[start] = child[end];
child[end] = temp;
}
}
This can be done using DFS procedure with a little modification:
(Assume the color of all nodes intially is WHITE)
Time complexity: O(n)
Space complexity: O(1)
void mirrortree(node* root)
{
if(root==null) return;
int numch = root->numchildren;
root->color = GREY;
for(int i=0;i<numch;i++)
{
if(root->next[i]->color==WHITE)
mirrortree(root->next[i]);
}
root->color=VISITED;
// now start swapping child nodes of this tree to convert it to mirror
int min=0, max=numch;
while(min<max)
{
node* tmp = root->next[min];
root->next[min] = root->next[max];
root->next[max] = tmp;
min++;max--;
}
}
Clean and Correct solution...Cheers!!!
typedef struct treeNode
{
int data;
listNode* childrenListHead;
} treeNode;
typedef struct listNode
{
treeNode* node;
listNode* next;
} listNode;
void reverseList(listNode* &head)
{
if(!head || !head->next)
return;
listNode* rest = head->next;
reverseList(rest);
head->next->next = head;
head->next = NULL;
head = rest;
}
void mirror(treeNode* root)
{
if(!root)
return;
listNode* n = root->childrenListHead;
while(n)
{
mirror(n->node);
n = n->next;
}
reverseList(root->childrenListHead);
}
- tetura June 07, 2010