Microsoft Interview Question Software Engineer in Tests
Country: India
Interview Type: In-Person
your logic would work only if the tree is a perfect binary tree. it will fail otherwise... suppose root has only right subtree with one children i.e - tree=> a c
answer should be
c - 2 0
a - 1 1
but as per your solution it would be
c - 1 0
a - 0 1
I think the soluin will work
if tree is
a
c
than the answer should be
a 0,1
c 1,0
and thats what the above solution will give
Here is my solution in C#. GetHeight method is used to calculate the height of the tree and called once before PrintXY method to calculate the height input.
static int xcoord = 0;
public static int GetHeight(TNode root)
{
if (root == null)
return -1;
else return Math.Max(GetHeight(root.left), GetHeight(root.right)) + 1;
}
public static void PrintXY(TNode node, int level, int height)
{
if (node != null)
{
PrintXY(node.left, level+1, height);
Console.WriteLine(node.data + "," + xcoord++ + "," + (height - level));
PrintXY(node.right, level+1, height);
}
}
Initialize baseX, and baseY to -1
Do and inorder traversal, and when processing a node its X and Y co-ordinates are computed as:
X = baseX+1
if (baseY==-1)
Y=0; baseY=height_of_node;
else
Y=height_of_node - baseY
Implementation:
int main() {
printCoord(root,0);
return 0;
}
void printCoord(Node *node, int height) {
if (!node) return;
int x, y;
static int baseX=-1;
static int baseY=-1;
printCoord(node->left,height+1);
x=baseX+1;
if (baseY==-1){
y=0; baseY=height;
}
else y=height-baseY;
cout << node->val << ": (" << x << ", " << y << ")" << endl;
}
In my above code forgot to add the recursive call to right Child. Here is the corrected code:
int main() {
printCoord(root,0);
return 0;
}
void printCoord(Node *node, int height) {
if (!node) return;
int x, y;
static int baseX=-1;
static int baseY=-1;
printCoord(node->left,height+1);
x=baseX+1;
if (baseY==-1){
y=0; baseY=height;
}
else y=height-baseY;
cout << node->val << ": (" << x << ", " << y << ")" << endl;
printCoord(node->right,height+1);
}
There is a recursive implementation
1.) get the root - in my case since I use a matrix it will be the most left-bottom Character
2.) recursively go inorder --> left (leftY = pY * 2), childX = pX - 1 then print the curr character then rightY = leftY + 1
Here is a java implementation:
public void printInorderCartesian(Character[][] tree) {
int rootX = tree.length - 1, rootY = 0;
printInorderCartesian(tree, rootX, rootY);
}
private void printInorderCartesian(Character[][] tree, int x, int y) {
int childX = x - 1;
int leftY = parentY << 1;
int rightY = leftY + 1;
if (x >= 0 && y < tree[0].length) {
printInorderCartesian(tree, childX, leftY)
System.out.println(tree[x][y]);
printInorderCartesian(tree, childX, rightY)
}
}
Posting implementation for feedback
class Node{
Node left;
Node right;
char data;
};
static int x, y;
void printTree(Node root){
x = -1;
y = -1;
printTreeRecursive(root);
}
void printTreeRecursive(Node root){
if(root == null)
return null;
if(root.left == null && x == -1){
x = 0;
y = 0;
}
if(root.left != null){
if(x != -1){
y--;
}
printTreeRecursive(root.left);
y++;
}
System.out.println("%c,%d,%d", root.data, x, y);
x++;
if(root.right != null){
y--;
printTreeRecursive(root.right);
y++;
}
}
I also tested the code and it does work for me using the data set in the question.
What data set are you using for testing?
How did you construct you binary tree?
Did you verify that the contents of your binary tree is correct?
Is there any additional information you can provide to help me reproduce what you might be seeing?
@CodeSpace: here is the tree I am constructing:
struct node* root = newNode (1);
root->left = newNode (2);
root->right = newNode (3);
root->left->left = newNode (4);
root->left->right = newNode (5);
root->right->left = newNode (6);
root->right->right = newNode (7);
root->right->left->left = newNode (8);
so it if of the form:
------------------------- 1---------------------------------
---------------------2----------3--------------------------
----------------4-------5----6------7--------------------
-----------------------------8-----------------------------
does the tree make sense?
@JustCoding: Thanks. I ran my code against your data set and the results I got is correct. See below. What are the results you are getting? Do you feel the results below is incorrect?
4,0,0
2,1,1
5,2,0
1,3,2
8,4,-1
6,5,0
3,6,1
7,7,0
you will note that 1 has 3 levels of nodes below it... so 1 should output 1, 3, 3
also, by the definition I have given above, 8 should output 8, 4, 0 since it is the 4th cardinal in the inorder traversal, and has 0 levels below it...
so I think you first need to find the height of the tree, and then use that value while giving the y-coordinate...
does this make sense?
yeah but never mind... it will become complicated if we try this... your solution appears to work fine...
actually @yakku should check and comment on the expected answer and compare against your solution... that will give better picture...
The questions states "...leftmost node is placed at point (0,0)..." So, this means that 4 (the left most node) will be at (0,0) and 1's y-axis will be 2 since it is 2 cardinal points on top of our reference point (0,0). 8 y-axis will be -1 since it is 1 cardinal point below the (0,0) reference point.
With the output you are expecting you can not have 4 at (0, 0) which is a requirement from the question.
Does this make sense?
You can easily note here that for any given node:
- JustCoding October 22, 2012the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;
Using these 2 pieces you can easily get the output shown above...
makes sense?