Microsoft Interview Question Software Engineer / Developers

  • microsoft-interview-questions
    0
    of 0 votes
    24
    Answers

    How to print the outside frame of a binary tree.

    1. the order is top to down, left to right, then down to top
    2. print all leftest node and rightest nodes
    3. print all leaf nodes
    4. print all nodes which only have 1 leaf

    100
               50                               150
         24          57                 130
      12     30          60                 132

    e.g:
    the output should be
    100, 50, 24, 12, 30, 57, 60, 130, 132, 150

    - Yaya on June 20, 2012 in United States Report Duplicate | Flag
    Microsoft Software Engineer / Developer Algorithm

Country: United States
Interview Type: In-Person


Comment hidden because of low score. Click to expand.
2
of 4 vote

I modify shondik's code, the entire idea is correct, just need a few adjustment

#include<stdio.h>
#include<stdlib.h>

struct node {
    struct node *left;
    struct node *right;
    int data;
};

struct node *newnode(int data)
{
        struct node *node=(struct node *)malloc(sizeof(struct node));
        node->data=data;
        node->left=NULL;
        node->right=NULL;
        return node;
}



void printBoundaryLeft(struct node *root)
{
	if(root==NULL)
		return;
	if(root->left)
	{
		printf("%d ",root->data);
		printBoundaryLeft(root->left);
	}
}

void printBoundaryLeaf(struct node *root)
{
	if(root==NULL)
		return ;
	else
	{
		printBoundaryLeaf(root->left);
		if(root->left==NULL||root->right==NULL)
			printf("%d ",root->data);

		printBoundaryLeaf(root->right);
	}
}


void printBoundaryRight(struct node *root)
{
	if(root==NULL)
		return;
	if(root->right)
	{

		printBoundaryRight(root->right);
		printf("%d ",root->data);
	}
}
void printBoundary(struct node *root)
{

	if(root)
	{
		printf("%d ",root->data);
		printBoundaryLeft(root->left);
		printBoundaryLeaf(root);
		printBoundaryRight(root->right);
	}

}

int main()
{
	struct node *root=newnode(100);
	root->left=newnode(50);
	root->right=newnode(150);
	root->left->right=newnode(57);
	root->left->right->right=newnode(60);
	root->left->left=newnode(24);
	root->right->left=newnode(130);
	root->right->left->right=newnode(132);
	root->left->left->left=newnode(12);
	root->left->left->right=newnode(30);

	printBoundary(root);


	return 0;
}

- kingoffreeze on July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

a few of the nodes are printed twice
minor adjustments will make it better

- Tushar on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This approach does not work when, say root only has right sub-tree.

- IntwPrep on December 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is called an Euler tour. Refer: [http]jrgalia.com/content/euler-tour-traversal-binary-search-tree for java implementation.

- rajarshi129 on October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

A simple approach would be is look at it as printing the 1st and last node at each level, and also all the leaves.
Algorithm:
1) Find the height of the tree. Say H. Then initialize two strings level[H][2], and leaves[2^H] arrays to NULL
2) Do a DFS by keeping track of the height and at each node X, say at height h
a) if level[h][0] is NULL then level[h][0]=X
b) else if X is a leaf then leaves.append(X)
c) else level[h][1]=X
3) Once done with the DFS then print nodes in level[h][0] (marks the beginning node at each level), then nodes within leaves array, and then those in level[h][1] (marks the last node at each level)

Time complexity: O(N)
Space complexity: O(N)

- IntwPrep on December 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is basically a boundary edge traversal.

void printBoundaryEdgesLeft(struct node *root)
{
	if(root->left)
        {
                printf("%d ",root->data);
		printBoundaryEdgesLeft(root->left);
        }
        else if(root->right)
        {
                printf("%d ",root->data);
		printBoundaryEdgesLeft(root->right);
        }
}

void printBoundaryEdgesLeaves(struct node *root)
{
	if(root)
	{
		printBoundaryEdgesLeaves(root->left);
		
		if( !(root->left) && !(root->right) )
			printf("%d ",root->data);
			
		printBoundaryEdgesLeaves(root->right);
	}
}

void printBoundaryEdgesRight(struct node *root)
{
	if(root->right)
        {
		printBoundaryEdgesRight(root->right);
                printf("%d ",root->data);
         }
        else if(root->left)
        {
		printBoundaryEdgesRight(root->left);
                printf("%d ",root->data);
        }
}

void printBoundaryEdges(struct node *root)
{
	if(root)
	{
		printf("%d ",root->data);
		printBoundaryEdgesLeft(root->left);
		
		printBoundaryEdgesLeaves(root->left);
                printBoundaryEdgesLeaves(root->right);
		
		printBoundaryEdgesRight(root->right);
	}
}

- Aashish on June 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you post a main function for this?..thanks in advance

- vineetsetia009 on June 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this will miss the non leaf nodes with only one child.
For example the 130 in the given tree

- nio on June 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@enihgad, i have modified the code. Now, its working for trees with one child also.
@vineetsetia009, call should be made as:
printBoundaryEdges(root);
I don't think there is any need of main function.

- Aashish on June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think ur code is still incorrect :
1) You are getting some elements printed twice.
2) Your code of method "printBoundaryEdgesRight" is incorrect , if you mind analysing it.

- BABA on June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please my answer.

- BABA on June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@BABA, its better to cite some examples where the code fails than to writing sarcastic comments. Thank you.

- Aashish on June 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey shondik,
Why would I put some example when your code have the problems I suggested for the given example in question.

- BABA on June 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the Java implementation. Here is in short what it does :
1.) doing preorder traversel
2.) keep if the node is on the most left or right side
3.) print nodes if they are end node or are most left or right node

public void printOutSideBoundries(TreeNode root) {
  printOutSideBoundries(root, true, true);
 }
 
 private void printOutSideBoundries(TreeNode node, boolean left, boolean right) {
  if (node != null) {
   if (node.left == null || node.right == null || left)
    System.out.format(“%s, ”, node.data);
   
   printOutSideBoundries(node.left, left, false);
   printOutSideBoundries(node.right, false, right);
 
   if (right && !(node.left == null || node.right == null || left))
    System.out.format(“%s,  ”, node.data);
  }
 }

- GKalchev on June 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Yaya : The tree structure is not clear to me. Could you please try to post the tree structure again.
Thanks.

- Begineer on June 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//   shondik's running code
#include<stdio.h>
#include<stdlib.h>
struct node {
    struct node *left;
    struct node *right;
    int data;
};
struct node *newnode(int data)
{
        struct node *node=(struct node *)malloc(sizeof(struct node));
        node->data=data;
        node->left=NULL;
        node->right=NULL;
        return node;
}


void   printBoundaryLeft(struct node *root)
{
        if(root==NULL)
            return;
        if(root->left)
        {
                printf("%d ",root->data);
                  printBoundaryLeft(root->left);
        }
        else  if(root->right)
        {
                printf("%d ",root->data);
                  printBoundaryLeft(root->right);
        }
}
void   printBoundaryLeaf(struct node *root)
{
        if(root==NULL)
            return ;
        else
        {
                printBoundaryLeaf(root->left);
                  if(root->left==NULL&&root->right==NULL)
                    printf("%d ",root->data);
                
                printBoundaryLeaf(root->right);
        }
}

void   printBoundaryRight(struct node *root)
{
        if(root==NULL)
            return;
        if(root->right)
        {
               
                  printBoundaryLeft(root->right);
                   printf("%d ",root->data);
        }
        else if(root->left)
            {
                
                  printBoundaryLeft(root->left);
                  printf("%d ",root->data);
            }
                
}
void  printBoundary(struct node *root)
{

        if(root)
        {
                printf("%d ",root->data);
                printBoundaryLeft(root->left);
                printBoundaryLeaf(root);
                printBoundaryRight(root->right);
        }
        
}
                
int main()
{
    struct node *root=newnode(1);
    root->left=newnode(2);
    root->right=newnode(3);
    root->left->right=newnode(4);
     root->left->right->left=newnode(13);
    root->left->left=newnode(5);
    root->right->right=newnode(7);
    root->right->left=newnode(12);
    
    printBoundary(root);
    
    
    return 0;
}

- Arya on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think all the nodes having one leaf node are not printed

- Tushar on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void DisplayPreOrder(TreeNode *nodePtr)
{
if(nodePtr)
{
cout<<"Data : "<<nodePtr->data<<endl;
DisplayPreOrder(nodePtr->Left);
DisplayPreOrder(nodePtr->Right);
}
}

- Shahid Iqbal on June 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I think the following algorithm can do it all :

1)This method would give left edge of the frame.
   Method1(root,arr) 
    {
        if(root) 
         {
            arr.append(root)
            Method1(root->left , arr)
         }
        else
         {
             return arr
         }
    }
2)This method will generate right edge og the frame.
   Method2(root,arr)
     {
         if(root)
          {
             arr.append(root)
             Method2(root->right , arr)
          }
         else
	  {
	     return arr
          }
     }
3) genrate_frame(root)
   {
      ARRAY_TYPE arr_left[],arr_right[],arr_inorder[];
      Method1(root,arr_left);
      Method2(root->right,arr_right);
      Inorder(root,arr_inorder);//This function returns inorder traversal of the tree.
      for elem in arr_inorder:
	{
        if(elem->left!=NULL && elem->right!=NULL)
           continue;
        if(elem in arr_left)
           continue;
        if(elem in arr_right)
           continue;
        filter.append(elem)
        }
      print arr_left
      print filter
      print reverse(arr_right)
   }

- BABA on June 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@BABA, inefficient code. Doesn't handle various cases.
Try the below tree:

10
	        / \
              15   12
              \    /
               7  10
              /   /
             2   25

- Aashish on June 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@shondik : Thank you , its a nice case which you pointed out.

- BABA on July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I request everyone to post algorithm rather than code. Most people here do not have time to go through many lines of code.

- DarkKnight on July 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we generalize saying that for
1) Left half of the root it is a pre order traversal
2) Right half of the root is an inorder traversal
??

- blah123 on November 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Initialize 3 lists left, bottom and right
2) Do a breadth first traversal but don't pop nodes of a level as u traverse it in order to keep track of the index of each node on the level
3) Check the following for each node
a) if index == 0 --> add node to left list
b) else if index == level.size() - 1 --> add node to right list
c) else
i) if node->left->left = null && node->left->right = null --> add node->left to bottom
ii) if (i) = true and node->right = null --> add node to bottom
iii) if (i) = false and node->right->left = null && node->right->right = null -> add node to bottom and node->right to bottom
4) do the breadth first traversal step

finally after the traversal if finished do:
1) print left from 0 to n
2) print bottom from 0 to n
3) print right from n to 0

- Mustapha on December 03, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More