Microsoft Interview Question
SDE1sCountry: United States
Interview Type: In-Person
@amazon engineer
Consider the following tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / / \
8 9 10 11 12
\
13
For the above input, if I'm not mistaken,
1) node 9 would be printed since it satisfies the condition
if (isRight && !isLeft && (node.left != null || node.right != null)
printTraversal (9, false, true).
2) Node 6 would be printed since it satisfies the condition
if(isLeft || (node.left == null && node.right == null))
printTraversal (6, true, false).
Correct me if I'm wrong.
My bad. Didn't look in to the recursive call thoroughly.
It would be printTraversal (9, false, false) and printTraversal (6, true, false).
Up voting the solution.
The solution wont work for a tree like
10
/ \
5 12
\
7
\
8
here 7 would be expected to be printed but it won't be.
@arun i dont think 6 will be printed.. because when u r moving from 3 to 6, printTraversal(6,false,false) will be called.
1
/ \
2 3
/ \
4 6
/
5
o/p should contain 4...
but acord., to the prgs posted in this site as well as in other sites o/p will not contain 4.
the best soln is to do bfs and keep track start and end nodes at each level...
please correct if i am wrong............
the above diagram was not clear so i posted again........
1
/ \
2 3
/ \
4 6
/
5
o/p should contain 4...
but acord., to the prgs posted in this site as well as in other sites o/p will not contain 4.
the best soln is to do bfs and keep track start and end nodes at each level...
please correct if i am wrong............
the above diagram was not clear so i posted again........
1
/ \
2 3
/ \
4 6
/
5
o/p should contain 4...
but acord., to the prgs posted in this site as well as in other sites o/p will not contain 4.
the best soln is to do bfs and keep track start and end nodes at each level...
please correct if i am wrong............
First solution I thought of was to do it in 3 steps, the left, bottom and right sides:
public static List<Integer> findPerimeter(final Node root){
if(root == null)
return Collections.<Integer> emptyList();
final List<Integer> perim = new ArrayList<Integer>();
perim.add(root.value);
leftSide(root, perim);
bottomInOrderAddToList(root, perim);
rightSide(root, perim);
return perim;
}
public static void leftSide(final Node node, final List<Integer> list){
if(node.left != null && node.left.left != null){
list.add(node.left.value);
leftSide(node.left, list);
} else{
return;
}
}
public static void bottomInOrderAddToList(final Node node, final List<Integer> list){
// pre-order traversal
if(node == null)
return;
bottomInOrderAddToList(node.left, list);
if(node.left == null && node.right == null)
list.add(node.value);
bottomInOrderAddToList(node.right, list);
}
public static void rightSide(final Node node, final List<Integer> list){
if(node.right != null && node.right.right != null){
rightSide(node.right, list);
list.add(node.right.value);
} else{
return;
}
}
// reference stackoverflow
void print_perimeter(struct node * root,int left,int right)
{
if(root == NULL)
return;
if(root)
{
if(right==0)
{
print("%d \n", root->key_value);
}
print_perimeter(root->left,left+1,right);
if(!root->left && !root->right && right>0)
{
print("%d \n", root->key_value);
}
print_perimeter(root->right,left,right+1);
if(left==0)
{
if(right!=0)
{
print("%d \n", root->key_value);
}
}
}
}
Interesting question.
This is how I would solve this:
1. Store the left-most node and right most node. <<Takes O(n) time.
2. Print the path from root to left most node. (slightly tweaked Pre-order traversal) <<Takes O(n) time.
3. Do an inorder traversal of the tree and print the node whenever it is a Leaf node (i.e. left and right children are NULL). Don't print anything if this leaf node happen to be the left or right most node that we saved in step 1. <<Takes O(n) time.
4. Print the path from right most node to root. (slightly tweaked Post-order traversal) <<Takes O(n) time.
Of course, we can do minor optimizations but the worst case time complexity would be O(n) and space complexity would be O(1)
It can be done in single go. Simply do level order traversal, whenever level change, add 1st node of that level, when level end, add last visited element and also keep checking element which has no child (leaf node) and add all of them. This will return required result.
I traverse the binary tree recursively:
public class BinaryTree {
public BinaryTree Left;
public BinaryTree Right;
public int Value;
}
/*
* action value meaning:
* 0, to print leftmost + leaves + rightmost
* 1, to print leftmost + leaves
* 2, to print rightmost + leaves
* 3, to print leaves
*/
public static Print(BinaryTree node, int action) {
if(node == null) {
throw new ArgumentNullException("node");
}
if(action != 3) {
// print current value
Console.Write("{0} ", node.Value);
}
int left_action = -1, right_action = -1;
switch(action) {
case 0: left_action = 1, right_action = 2; break;
case 1: left_action = 1, right_action = 3; break;
case 2: left_action = 3, right_action = 1; break;
case 3: left_action = 3, right_action = 3; break;
default:
throw new ArgumentException("action: out of range!");
}
if(node.Left != null) Print(node.Left, left_action);
if(node.Left == null && node.right == null && action == 3) {
// print current value
Console.Write("{0} ", node.Value);
}
if(node.right != null) Print(node.Right, right_action);
}
function PrintPerimeter(Node n, bool isLeft, bool isRight) {
if( isLeft )
print n
PrintPerimeter(n->left,isLeft,false);
if ( n-> left == NULL AND n-> right == NULL)
print n
PrintPerimeter(n->right,false,isRight);
if ( isRight )
print n
}
Modify version of your code which will take care of border cases also
void printParameter (tree *root, bool left, bool right)
{
if (root)
{
if (left && !(!root->l_child && !root->r_child))
printf ("%d ", root->key);
printParameter (root->l_child, left, false);
if (!root->l_child && !root->r_child)
{
printf ("%d ", root->key);
return;
}
printParameter (root->r_child, false, right);
/*For satisfying condition that root should not be printed twice*/
if (right && !left)
printf ("%d ", root->key);
}
}
/*
Helper function to print the perimeter nodes of the binary tree, recursively
Algorithm:
1) Print the left edge of binary tree
2) Print the leaves of binary tree
3) Print the right edge of binary tree
*/
void PrintPerimeterofBinaryTree(binaryTreeNode *root, int leftedge, int rightedge)
{
if(!root)
return;
if(leftedge)
printf("%d \n", root->data);
PrintPerimeterofBinaryTree(root->left, leftedge && 1, 0);
if(!leftedge && !rightedge && (!(root->left) || !(root->right)))
printf("%d \n", root->data);
PrintPerimeterofBinaryTree(root->right, 0, rightedge && 1);
if(rightedge)
printf("%d \n", root->data);
}
/*
Function to print the perimeter nodes of the binary tree
Algorithm:
1) Print the root of binary tree
2) Print the perimeter nodes of left binary tree
3) Print the perimeter nodes of right binary tree
Time Complexity: O(n)
Space Complexity: is of the recursive function stack that is being used
*/
void PrintPerimeterofCompleteBinaryTree(binaryTreeNode *root)
{
if(!root)
return;
printf("%d \n", root->data);
PrintPerimeterofBinaryTree(root->left, 1, 0);
PrintPerimeterofBinaryTree(root->right, 0, 1);
}
private void VisitPerimeter(BinaryTreeNode<T> node, BinaryTreeNodeVisitDelegate<T> visitor, bool isLeft, bool isRight)
{
if (node == null) return;
if (isLeft || isRight)
visitor(node);
else if ((node.Left == null) && (node.Right == null))
visitor(node);
VisitPerimeter(node.Left, visitor, isLeft, false);
VisitPerimeter(node.Right, visitor, false,isRight);
}
public void VisitPerimeter(BinaryTreeNodeVisitDelegate<T> visitor)
{
VisitPerimeter(root, visitor, true, true);
}
The question is actually a lot trickier than it seems.
I am a CS student in a high school for gifted youth in Israel. I used your site as a source for questions for our final exams, and I gave this question.
One of the students from a different class approached me after the test and pointed out that the question is not well defined, giving the following tree as an example:
1
/
2
/
3
\
4
\
5
/
6
Since the tree's "width" is 1, all the nodes are on the perimeter, but none of the algorithms will be able to handle it.
Based ont the above phrasing of the question, it appears that the student is right.
I don't know how the question was originally phrased, but it should be re-phrased (unless this is exactly what the testers wanted to check...)
This is my solution (in C).
it handles Yossi's example too.
#include "stdio.h"
typedef struct Node_Obj
{
struct Node_Obj* left;
struct Node_Obj* right;
int val;
} Node;
void
print_left_perimiter(Node* node)
{
if (node == NULL)
{
return;
}
if (node->left == NULL && node->right == NULL)
{
/* node is a leaf - don't print it !t */
return;
}
printf("%d ", node->val);
if (node->left)
{
print_left_perimiter(node->left);
}
else if (node->right)
{
print_left_perimiter(node->right);
}
}
void
print_right_perimiter(Node* node)
{
if (node == NULL)
{
return;
}
if (node->right)
{
print_right_perimiter(node->right);
}
else if (node->left)
{
print_right_perimiter(node->left);
}
else
{
/* node is a leaf - don't print it !t */
return;
}
printf("%d ", node->val);
}
void print_leaves_left_to_right(Node* node)
{
if (node == NULL)
{
return;
}
/* leaft ? print it */
if (node->left == NULL && node->right == NULL)
{
printf("%d ", node->val);
return;
}
/* not a leaft ? continue traversing */
print_leaves_left_to_right(node->left);
print_leaves_left_to_right(node->right);
}
void print_perimiter(Node* root)
{
if (root == NULL)
{
return;
}
/*
if root is a leaf, we will print it in print_leaves_left_to_right,
so we verify it is not the case, before we print it
*/
if (root->left || root->right)
{
printf("%d ", root->val);
}
print_left_perimiter(root->left);
print_leaves_left_to_right(root);
print_right_perimiter(root->right);
}
Your solution does cover the example I gave, but it will print values twice (the leaf 6 will be printed 3 times), since the left and the right hand sides are the same nodes (and 6 is on both sides and is also a leaf).
The only way I see around it, is to use a linked list of Tree nodes (yechhh) so you can make sure every item that you add is not already in the list, and then in the end you print the list. If it is given that the values in the tree are unique, then you can use a list of integers.
Of course the question would be much more fair if you were to assume that the tree is full except for the leaves level and that the values are uniqe.
Yossi
Hi Yossi,
Try to compile and run my code.
You will see that every node is printed once (1 2 3 4 5 6)
my print_right_perimiter and print_left_perimiter does not print leaves, the leaves are printed by print_leaves_left_to_right. This guarantees that every value is printed only once.
My solution considers your example as a tree which contains only left perimiter, actually the whole tree is the left perimiter (and node 6 is considered a leaf).
// Printing root node, as it is always part of perimeter.
std::cout<<myBST->value<<" ";
if(myBST->left)
perimeterTraversal(myBST->left, true, true); // passing true, true. root->left is always on perimeter and belongs to left subtree.
if(myBST->right)
perimeterTraversal(myBST->right, true, false); // passing true, false. root->right is always on perimeter and doesn't belongs to left subtree.
void perimeterTraversal(BST *tree, bool isOnPerimeter, bool isInLeftSubtree)
{
if(tree)
{
if(tree->left == NULL && tree->right == NULL)
{
// Node is a leaf node, which is always on perimeter.
std::cout<<tree->value<<" ";
}
else
{
// Node is not a leaf node.
if(isOnPerimeter) // This means that current node is on perimeter.
{
std::cout<<tree->value<<" ";
if(tree->left != NULL && tree->right == NULL) // If there is only left child, traverse that and it would be on perimeter.
perimeterTraversal(tree->left, true, isInLeftSubtree);
else if(tree->left == NULL && tree->right != NULL) // If there is only right child, traverse that and it would be on perimeter.
perimeterTraversal(tree->right, true, isInLeftSubtree);
else if(tree->left != NULL && tree->right != NULL) // If there are two children, check current node belongs to which subtree.
{
if(isInLeftSubtree) // It's a part of left subtree, left child will be on perimeter not right.
{
perimeterTraversal(tree->left, true, isInLeftSubtree);
perimeterTraversal(tree->right, false, isInLeftSubtree);
}
else // It's a part of right subtree, right child will be on perimeter not left.
{
perimeterTraversal(tree->left, false, isInLeftSubtree);
perimeterTraversal(tree->right, true, isInLeftSubtree);
}
}
}
else // This node is not on perimeter, travese both child for leaf nodes.
{
perimeterTraversal(tree->left, false, isInLeftSubtree);
perimeterTraversal(tree->right, false, isInLeftSubtree);
}
}
}
}
you have to do 3 task for making it simple ,break in three process
1)print all the left node.
2)print all the leaf.
3)print all the right node.
struct node
{
int data;
node *l,*r;
};
#include<iostream>
using namespace std;
node *create_node(int data);
void perimeter(node *root);
void print_r_child(node *root);
void print_l_child(node *root);
void print_leaves(node *root);
int main()
{
node * root = NULL;
root = create_node(1);
root->l = create_node(2);root->r = create_node(3);
root->l->l = create_node(4);root->l->r = create_node(5);
root->r->l = create_node(6);root->r->r = create_node(7);
root->l->l->l = create_node(8);root->l->l->r = create_node(9);
root->l->r->l = create_node(10);root->l->r->r = create_node(11);
perimeter(root);
return 0;
}
void perimeter(node *root)
{
if(root) cout<<root->data<<" ";
print_l_child(root->l);
print_leaves(root);
print_r_child(root->r);
}
void print_l_child(node *root)
{
if(root->l!=NULL)
{
cout<<root->data<<" ";;
print_l_child(root->l);
}
}
void print_r_child(node *root)
{
if(root->r!=NULL)
{
print_r_child(root->r);
cout<<root->data<<" ";
}
}
node *create_node(int data)
{
node *newnode = new node;
newnode->data = data;
newnode->l = newnode->r = NULL;
return newnode;
}
void print_leaves(node *root)
{
if(!(root->l && root->r))
{
cout<<root->data<<" ";
return;
}
if(root->l) print_leaves(root->l);
if(root->r) print_leaves(root->r);
}
psuedocode:
1) preorder of left subtree only (including root but excluding leafs)
2) leafs of left subtree
3) leafs of right subtree
4) postorder of right subtree only (excluding leafs)
Code:
void specialPreorder (tree *root)
{
if (root)
{
if (! root->l_child && ! root->r_child)
{
return;
}
printf ("%d ", root->key);
specialPreorder (root->l_child);
}
}
void leaf (tree *root)
{
if (root)
{
if (! root->l_child && ! root->r_child)
{
printf ("%d ", root->key);
return;
}
leaf (root->l_child);
leaf (root->r_child);
}
}
void specialPostorder (tree *root)
{
if (root)
{
if (! root->l_child && ! root->r_child)
{
return;
}
specialPostorder (root->r_child);
printf ("%d ", root->key);
}
}
void perimeter (tree *root)
{
if (!root)
return;
printf ("\n");
specialPreorder (root);
leaf(root->l_child);
leaf(root->r_child);
specialPostorder (root->r_child);
printf ("\n");
}
static bool flag = false;
static bool returnFlag = false;
static void PrintPrimeter(TreeNode cur)
{
if (cur != null)
{
if (cur.Left != null || cur.Right != null)
{
//Do PreOrder and Print each number on the road.
if (!flag) Console.WriteLine(cur.Value);
PrintPrimeter(cur.Left);
PrintPrimeter(cur.Right);
//Print everything when we quite the recursion
if (returnFlag) Console.WriteLine(cur.Value);
}
else
{
//When we hit the first leaf node.
//Start to print nothing but all leaf
flag = true;
Console.WriteLine(cur.Value);
//Until we hit the most right node which is also the last leave node
//We set the returnFlag to quite the recursion
if (cur == MostRightTreeNode) returnFlag = true;
}
}
}
static TreeNode MostRightTreeNode = null;
static bool rflag = false;
static void FindRightMostNode(TreeNode cur)
{
if (cur != null)
{
if (cur.Left != null || cur.Right != null)
{
if (!rflag) FindRightMostNode(cur.Right);
if (!rflag) FindRightMostNode(cur.Left);
}
else
{
MostRightTreeNode = cur;
rflag = true;
}
}
}
public static printPremier (Node root, State s) {
if (root == null) return;
switch (s) {
case ROOT:
System.out.println(root.value());
printPremier(root.left(),State.LEFT);
printPremier(root.right(),State.RIGHT);
case LEFT:
System.out.println(root.value());
printPremier(root.left(),State.LEFT);
printPremier(root.right(),State.INTERNAL);
break;
case INTERNAL:
if (root.left() == null && root.right() == null) {
System.out.println(root.value());
} else {
printPremier(root.left(),State.INTERNAL);
printPremier(root.right(),State.INTERNAL);
}
break;
case RIGHT:
printPremier(root.left(),State.INTERNAL);
printPremier(root.right(),State.RIGHT);
System.out.println(root.value());
break;
}
}
How about this:
1) Root node and leaf nodes will be there in the perimeter.
For all other nodes:
2) If the depth of the tree is n, then for first and last nodes of any level i will be in the perimeter.
3) the order in which the answer has to be printed can be determined by traversing the tree and checking for each node if it is filtered out by step 1 or 2.
void PrintPerimeter(node *root, bool isleft, bool isright)
{
if (!root)
return;
if (!root->l && !root->r)
{
printf("%d ", root->data);
return;
}
if (isleft)
printf("%d ", root->data);
PrintPerimeter(root->l, isleft, false);
PrintPerimeter(root->r, false, isright);
if (isright)
printf("%d ", root->r);
}
int main()
{
......
PrintPerimeter(root,true,true);
}
#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0
struct tree{
struct tree *lc;
int data;
struct tree *rc;
};
void insert(struct tree **root,int num)
{
struct tree *temp=*root;
if(*root==NULL)
{
(*root)=(struct tree *)malloc(sizeof(struct tree));
(*root)->lc=NULL;
(*root)->rc=NULL;
(*root)->data=num;
return;
}
else
{
if(num<temp->data)
{
insert(&(temp->lc),num);
}
else
{
insert(&(temp->rc),num);
}
}
}
void treeleftperi(struct tree *root,int a)
{
if(root==NULL)
return;
if(a==0)
{
printf(" %d",root->data);
}
if(root->rc!=NULL && a==0 && root->lc==NULL)
{
printf(" %d",root->rc->data);
}
treeleftperi(root->lc,0);
treeleftperi(root->rc,1);
}
void treerightperi(struct tree *root,int a)
{
if(root==NULL)
return;
if(a==1)
{
printf(" %d",root->data);
}
if(root->lc!=NULL && a==1 && root->rc==NULL)
{
printf(" %d",root->lc->data);
}
treerightperi(root->rc,1);
treerightperi(root->lc,0);
}
void treeperi(struct tree *root)
{
treeleftperi(root->lc,0);
treerightperi(root->rc,1);
}
int main()
{
struct tree *st=NULL;
int arr[]={50,30,70,20,40,60,80,21,65};
int n=sizeof(arr)/sizeof(arr[0]);
int i;
for(i=0;i<n;i++)
{
insert(&st,arr[i]);
}
printf("\n");
treeperi(st);
}
#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0
struct tree{
struct tree *lc;
int data;
struct tree *rc;
};
void insert(struct tree **root,int num)
{
struct tree *temp=*root;
if(*root==NULL)
{
(*root)=(struct tree *)malloc(sizeof(struct tree));
(*root)->lc=NULL;
(*root)->rc=NULL;
(*root)->data=num;
return;
}
else
{
if(num<temp->data)
{
insert(&(temp->lc),num);
}
else
{
insert(&(temp->rc),num);
}
}
}
void treeleftperi(struct tree *root,int a)
{
if(root==NULL)
return;
if(a==0)
{
printf(" %d",root->data);
}
if(root->rc!=NULL && a==0 && root->lc==NULL)
{
printf(" %d",root->rc->data);
}
if(a==1 && root->rc!=NULL && root->lc==NULL)
{
printf(" %d",root->rc->data);
}
treeleftperi(root->lc,0);
treeleftperi(root->rc,1);
}
void treerightperi(struct tree *root,int a)
{
if(root==NULL)
return;
if(a==1)
{
printf(" %d",root->data);
}
if(root->lc!=NULL && a==1 && root->rc==NULL)
{
printf(" %d",root->lc->data);
}
if(a==0 && root->lc!=NULL && root->rc==NULL)
{
printf(" %d",root->lc->data);
}
treerightperi(root->rc,1);
treerightperi(root->lc,0);
}
void treeperi(struct tree *root)
{
treeleftperi(root->lc,0);
treerightperi(root->rc,1);
}
int main()
{
struct tree *st=NULL;
int arr[]={50,30,70,20,40,60,80,21,65,22,23};
int n=sizeof(arr)/sizeof(arr[0]);
int i;
for(i=0;i<n;i++)
{
insert(&st,arr[i]);
}
printf("\n");
treeperi(st);
}
It is correct
Very simple solution:
1. print all the left perimeter nodes except the leaf
2. print all the leaves in the tree
3. print all the right perimeter nodes except the leaf
Overall running time: O(n)+O(n)+O(n) = O(n)
void print_perimeter(Tree t)
{
if(t == null) return "";
Tree head = t;
// Print left perimeter except the leaf node
while(head.left != null)
{
print(head.value);
head = head.left;
}
// print all the leaves using help function left_print... see below
leaf_print(t);
//print all the right perimeter nodes in reverse manner except leaf node
head = t;
ArrayList<Tree> list = new ArrayList<Tree>();
while(head.right != null)
{
list.add(head.value);
head = head.left;
}
for(int i=list.size()-1; i>=0; i--)
print(list.get(i));
}
// help function to print leaves
void leaf_print(Tree t)
{
if(t.left == null && t.right == null)
{print(t.value)
return "";
}
if(t.left != null)
leaf_print(t.left);
if(t.right != null)
leaf_print(t.right);
}
void PLB(Node *root){
if (root != NULL){
if (root->left == NULL && root->right == NULL) return;
else if (root->left != NULL){
cout << root->data << "\n";
PLB(root->left);
}
else if (root->right != NULL){
cout << root->data << "\n";
PLB(root->right);
}
}
}
void leafs(Node *root){
if (root != NULL){
if (root->left == NULL && root->right == NULL) cout << root->data << "\n";
if (root->left != NULL) leafs(root->left);
if (root->right != NULL) leafs(root->right);
}
}
void PRB(Node *root){
if (root != NULL){
if (root->left == NULL && root->right == NULL) return;
if (root->right != NULL) PRB(root->right);
else if(root->left != NULL) PRB(root->left);
cout << root->data << "\n";
}
}
void perimeterPrint(Node *root){
cout << "\nPerimeter Print\n";
PLB(root);
leafs(root->left);
leafs(root->right);
PRB(root->right);
}
Here's a very simple solution thats O(n):
- amazon engineer May 04, 2013