Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
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)
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);
}
}
I think this will miss the non leaf nodes with only one child.
For example the 130 in the given tree
@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.
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, its better to cite some examples where the code fails than to writing sarcastic comments. Thank you.
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);
}
}
// 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;
}
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, inefficient code. Doesn't handle various cases.
Try the below tree:
10
/ \
15 12
\ /
7 10
/ /
2 25
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
I modify shondik's code, the entire idea is correct, just need a few adjustment
- kingoffreeze July 01, 2012#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; }