Microsoft Interview Question Software Engineer / Developers
Your "printTree" function will return 0 to the main().
A little modification of your code is required:
void printTree(node *root,int i,int j,int a[])
{
static int len;
if(root)
{
if(!root->left && !root->right)
cout<<root->data<<" ";
else if(i>0 && j==0)
cout<<root->data<<" "; //printing left nodes
else if(i==0)
{
a[j]=root->data;
len=j;
}
fun(root->left,i+1,j,a);
fun(root->right,i,j+1,a);
}
return len;
}
void main()
{
node *root;
root=createTree(root); //this creates the tree
int a[50];
for(int len=printTree(root,0,0,a);len>=0;len--)
{
cout<<a[len]<<" ";
}
}
Hi what if the tree is level 4... then how will the output look like??
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Output: 2 4 8 9 10 11 12 13 14 15 7 3 1?
What about 5 and 6??
There are 2 problems with the above code.
Leftmost external node will be printed twice. To avoid that put printing external node in else block. That way rightmost external node has to be printed in the wrapper method.
Secondly j value is returned wrong. You need to collect j value from second printTree call. And collect only if previous method returned non zero.
Yes, you are right.
1. The condition to check leaf should be in else if block instead of if.
else if(!root->left && !root->right
2. The j value returned from the recursive call should be stored. But we need the count of only the rightmost nodes. So we return j in case it's the rightmost node else return j-1:
j=printNode(root->right, i,j+1,a) - 1;
if(!i)
return j;
else
return j-1;
Yes, you are right.
1. The condition to check leaf should be in else if block instead of if.
else if(!root->left && !root->right
2. The j value returned from the recursive call should be stored. But we need the count of only the rightmost nodes. So we return j in case it's the rightmost node else return j-1:
j=printNode(root->right, i,j+1,a) - 1;
if(!i)
return j;
else
return j-1;
int PrintTree(node* root)
{
if (!root)
{
return 0;
}
PrintLeftMostNodesTopDown(root->leftChild);
PrintLeaves(root);
PrintRightMostNodesBottomUp(root);
return 1;
}
void PrintLeftMostNodesTopDown(node *root)
{
if((root) && (root->leftChild))
{
cout << root << ", ";
}
else return;
PrintLeftMostNodesTopDown(root->leftChild);
}
PrintLeaves(node *root)
{
if(!root) return;
if(!(root->leftChild) || !(root->rightChild))) //this is leaf node
{
cout << root->data << ", ";
}
PrintLeaves(root->leftChild);
PrintLeaves(root->rightChild);
}
void PrintRightMostNodesBottomUp(node *root)
{
if((root) && (root->rightChild))
{
PrintRightMostNodesBottomUp(root->rightChild);
}
else return;
cout << root << ", ";
}
Forgot a correction i+1
---------------------------------------------------------------------------------
void printTree (node * root,int i)
{
int j;
if(root==NULL) return;
printTree(root->rlink,i+1);
for (j=1;j<=i;j++)
{
printf(" ");
}
printf("%d",root->info);
printTree(root->llink,i+1);
}
class Node {
int data;
Node left;
Node right;
public Node() { data = 0; left = null ; right = null ; }
}
public class BinaryTree {
private static final int N = 11;
private static Node root;
private static int [] A = {42, 98, 85, 9, 5, 95, 34, 12, 48, 8, 80};
public static void main(String [] args) {
root = buildBinaryTree(root);
printBinaryTree(root);
System.out.println();
printLeftLeafRight(root);
}
public static void printLeftLeafRight(Node root) {
printLeft(root);
System.out.println();
printRight(root);
System.out.println();
printLeafs(root);
System.out.println();
System.out.println(root.data);
}
public static void printLeafs(Node node) {
if (null == node) { return ; }
else {
printLeafs(node.left);
if ((null == node.left) && (null == node.right)) {
System.out.print(node.data + " ");
}
printLeafs(node.right);
}
}
public static void printLeft(Node node) {
if (null == node.left) { return ;}
else if (null == node.left.left && null != node.left.right) {
System.out.print(node.left.data);
} else {
while (null != node.left.left) {
System.out.print(node.left.data + " ");
node = node.left;
}
if (node.left.right != null) {
System.out.print(node.left.data);
}
}
}
public static void printRight(Node node) {
if (null == node.right) { return;}
else if (null == node.right.right && null != node.right.left) {
System.out.print(node.right.data);
}
else {
while (null != node.right.right) {
System.out.print(node.right.data + " ");
node = node.right;
}
if (node.right.left != null) {
System.out.print(node.right.data);
}
}
}
public static Node buildBinaryTree(Node node) {
Random rand = new Random();
for (int i=0; i<N; i++) {
int nodeData = rand.nextInt(100);
System.out.print(A[i] + " ");
//System.out.print(nodeData + " ");
node = insertIntoBinaryTree(node, A[i]);
}
System.out.println();
return node;
}
public static void printBinaryTree(Node node) {
if (null == node) { return ;}
else {
printBinaryTree(node.left);
System.out.print(node.data + " ");
printBinaryTree(node.right);
}
}
public static Node insertIntoBinaryTree(Node node, int value) {
if (null == node) { return newNode(value); }
else {
if (value <= node.data) {
node.left = insertIntoBinaryTree(node.left, value);
} else {
node.right = insertIntoBinaryTree(node.right, value);
}
return node;
}
}
public static Node newNode(int value) {
Node node = new Node();
node.data = value;
return node;
}
}
The question is not unclear, Anonymous, the example of output u gave is right. Vamsair, i like your solution, that is how i did as well.
MS IDC makes fool of people.
People have to come to office on weekends due to workload and do night outs, no work life balance. They pay 10-20% more make people labour.
Do take the feedback from employees before joining MS.
And work is junk, all junk wor from Redmond is transferred to IDC. Ask any team, whether they design, implement products or just do porting or maintenance or make tools.
public void WriteTreeEdge(Tree t)
{
if (t == null) return;
PrintLeftAndLeaves(t);
PrintRight(t);
}
private void Write(Tree t)
{
Console.WriteLine(t.data);
}
private bool ContainsChild(Tree t)
{
if (t.Left != null || t.Right != null)
return true;
return false;
}
private void PrintRight(Tree t)
{
if (t == null) return;
if (ContainsChildren(t))
{
PrintRight(t.Right);
}
Write(t);
}
private void PrintLeftAndLeaves(Tree t)
{
Stack<Tree> s = new Stack<Tree>();
bool isEdgeDone = t.Left != null;
s.Push(t.Right);
s.Push(t.Left);
while (s.count > 0)
{
Tree cur = s.Pop();
if (cur == null) continue;
if (!isEdgeDone)
{
Write(cur);
if (cur.Left == null) isEdgeDone = true;
}
if (!ContainsChild(cur))
{
Write(cur); //is leaf node
}
else
{
s.Push(cur.Right);
s.Push(cur.Left);
}
}
}
Here I combined the printLeft with printLeaves, but I couldn't quickly come up with an algorithm
that can also combine the right-most edges. I think a fully recursive approach could handle all 3 cases
with one traversal.
That said, edge traversal is very cheap for large balanced trees. O(LogN), though worst case is O(N), when
the tree is a simple list.
Either way, algorithm is O(N + LogN) on average or O(2N) at worst which are both O(N).
use cases: Needs clarification about behavior
1) full tree
2) Missing left node on left side
3) Missing right node on right side
4) Missing one leaf
Idea
1) Traverse the tree, store the leaf info
2) Traverse the left, print left, in pre order
3) Print leaf
4) Traverse the right, print right in post order
5) Print Root
The above answers are all flawed.
public void WriteTreeEdge(Node* t)
{
if (t == null) return;
PrintLeft（t->left）
PrintLeaves(t);
PrintRight(t);
}
private void PrintLeft (Node* t)
{
if(t == null) return;
if(t->left == NULL && t->Right == null)
return; //leaf
print(t->data);
if (t->left != NULL)
t = t->left;
else
t = t->Right;
PrintLeft (t);
}
private void PrintRight (Node* t)
{
if(t == null) return;
if(t->left == NULL && t->Right == null)
return; //leaf
if (t->Right!= NULL)
t = t->Right;
else
t = t->left;
print(t.data);
}
private void PrintLeaf (Node* t)
{
if(t == null) return;
PrintLeaf (t->left);
if(t->left == NULL && t->Right == null)
{
print(t->data);
return; //leaf
}
PrintLeaf (t->right);
}
val corresponf to root = -INT_MAX
val for left most tree is 0
val for right most part is -1
for other nodes val is some negative number
for leaf node the value val is not checked before printing
for other node this val value is chked before printing
antiprint(root,val=-INT_MAX){
if(root->left){
if(val==-INTMAX || val==0 ) { //left most part of tree
print root->data;
antiprint(root->left,0);
}
elseif(val<0)//right child of left most part
antiprint(root->left,val-1);
}
elseif(!root->right) print root->data; //leaf
else { //right
if(val==-1 || val==-INT_MAX) {//right most part of tree
antiprint(root->right,-1);
print root->data;
}
elseif(val==0)
antiprint(root->right,-2);
elseif(val<0)
antiprint(root->right,val-1);
}
}
void printLLeaves(Tree * rt)
{
if (rt == NULL) return;
while (rt -> right != NULL)
{
rt = rt ->right;
}
cout<<" "<<rt ->data<<" ";
}
void printLBoundary(Tree * rt)
{
if (rt == NULL) return ;
cout<<" "<<rt ->data<<" ";
printLBoundary( rt->left);
printLLeaves( rt->right);
}
void printRLeaves(Tree * rt)
{
if (rt == NULL) return;
while (rt -> left != NULL)
{
rt = rt ->left;
}
cout<<" "<<rt ->data<<" ";
}
void printRBoundary(Tree * rt)
{
if (rt == NULL) return ;
printRLeaves( rt->left);
printRBoundary( rt->right);
cout<<" "<<rt ->data<<" ";
}
//this has to be called by your prog
void printBoundary(Tree * rt)
{
if(rt == NULL) return ;
printLBoundary(rt->left);
printRBoundary(rt->right);
cout<<" "<<rt->data<<" ";
}
public Node printLeftPreOrder(Node n){
if(n == null){
return n;
}
System.out.print(n.value);
n.left = printLeftPreOrder(n.left);
printLeaf(n.right);
return n;
}
public void printLeaf(Node n){
if(n==null)
return;
if(n.left == null && n.right == null){
System.out.print(n.value);
return;
}
printLeaf(n.left);
printLeaf(n.right);
}
public Node printRightPostOrder(Node n){
if(n == null)
return n;
printLeaf(n.left);
n.right = printRightPostOrder(n.right);
System.out.print(n.value);
return n;
}
public void printTiangle(Node n){
if(n == null)
return;
printLeftPreOrder(n.left);
printRightPostOrder(n.right);
System.out.print(n.value);
}
void Bst::microsoftTree(int rear,int front,Bst **arr)
{
if (rear <= front && arr[rear] != NULL)
{
if (arr[rear]->left != NULL)
{
if (arr[rear]->left->left != NULL || arr[rear]->left->right != NULL)
{
cout << arr[rear]->left->data<<" ";
}
arr[++front] = arr[rear]->left;
}
if (arr[rear]->right != NULL)
{
arr[++front] = arr[rear]->right;
}
microsoftTree(rear+1,front,arr);
if (arr[rear]->right != NULL)
{
if (arr[rear]->right->right != NULL || arr[rear]->right->left != NULL)
{
cout << arr[rear]->right->data<<" ";
}
}
}
else
{
for (int i=0;i<=front;i++)
{
if (arr[i]->left == NULL && arr[i]->right == NULL)
{
cout << arr[i]->data<<" ";
}
}
}
}
Hope it will help just print root at the end :)
1. push root in stack s, do BFS
2. at BFS of every layer,
- print the first node -> this is the leftmost node
- for other nodes of the same layer, check if they are leaves -> put in queue q
- if they are last nodes of the layer push them in a stack s
3. after BFS is complete, you will have printed the left nodes
4. now print the queue q which contains the leaf nodes
5. finally print the stack..this will print the rightmost nodes and root in bottom-top order
Does this solution seem all right?
void print( tree * root){
If ( root ==null)
Return;
Stack * s= new stack;
S.push( root);
While(root->left)
{
Root = root->left;
Cout << root->data;
s.push(root);
}
While(s.size() > 1)
{
Tree * node = s.pop();
Printleaves(node);
}
Printrightpath(s.pop);
Delete s;
}
Printleaves( tree* node){
If (! Node) return;
If ( ! node->right) return;
Tree* right = node-> right;
Print( right);
}
void print( tree* node)
{
If ( !node->left &&! node->right){
cout << node->data;
}
If( node->left)
Print( node->left);
If( node->right)
Print( node->right);
}
Void Printrightpath( tree* node){
If(node->right == null) {cout << node->right; return;}
Printrightpath( node->right);
cout << node-> data;
Return;
}
hope this simple implementation should work:
void FlipOrder(Node* root)
{
if (root == null) return;
if( root->left)
{
Print(Node->left->data);
FlipOrder(Node->left;
}
if( root->right)
{
FlipOrder(Node->right->data);
Print(Node->right->data);
}
Print(Node->data);
}
If it's like a triangle covering the leftmost, leaves and the rightmost nodes of the tree without the inner nodes, this could be a possible solution:
- Robben May 25, 2010void wrapper(node *root)//wrapper function to make a call to the recursive function
{
int a[];//to store the rightmost nodes
int j = printTree(root,0,0,a);
j--;//rightmost leaf already printed
while(j>0)
{
cout<<a[j];//Print rightmost nodes
j--;
}
}
int printTree(node *root, int i,int j,int a[])
{
if(!root)
return;
if(i>0 && !j)//have traversed only left in the tree,no right branches taken
cout << root->data;//Print leftmost nodes
else if(!i)//No left branches taken
right[j]=root->value;//storing values to print in reverse order
if(!root->left && !root->right)//Printing the leaf nodes
cout << root->value;
printNode(root->left,i+1,j,a);//if traversing left increase i by 1
printNode(root->right,i,j+1,a);//if traversing right increase j by 1
return j;//return the no. of rightmost nodes present in the tree
}