## Microsoft Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

Here's a very simple solution thats O(n):

``````public static void findPerimeter(final Node root){
printTraversal(root, true, true);
}

public static void printTraversal(final Node node, boolean isLeft, boolean isRight){
// pre-order traversal
if(node == null)
return;

if(isLeft || (node.left == null && node.right == null))
System.out.print(node.value+" ");
printTraversal(node.left, isLeft ? true : false, false);
printTraversal(node.right, false, isRight ? true : false);
if(isRight && !isLeft && (node.left != null || node.right != null))
System.out.print(node.value+" ");

}``````

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@arun i dont think 6 will be printed.. because when u r moving from 3 to 6, printTraversal(6,false,false) will be called.

Comment hidden because of low score. Click to expand.
0

what if the tree is

``````1
/       \
2         3
\      /    \
4   5    6
/   \
7     8``````

should 4 be printed or not..?

Comment hidden because of low score. Click to expand.
0

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............

Comment hidden because of low score. Click to expand.
0

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............

Comment hidden because of low score. Click to expand.
0

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............

Comment hidden because of low score. Click to expand.
0

4 and 6 are left child and right child of 3.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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>();

leftSide(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){
leftSide(node.left, list);
} else{
return;
}
}

public static void bottomInOrderAddToList(final Node node, final List<Integer> list){
// pre-order traversal
if(node == null)
return;

if(node.left == null && node.right == null)
}

public static void rightSide(final Node node, final List<Integer> list){
if(node.right != null && node.right.right != null){
rightSide(node.right, list);
} else{
return;
}
}``````

Comment hidden because of low score. Click to expand.
0

This code is wrong. It won't print the root node value.

Comment hidden because of low score. Click to expand.
0

This code is wrong, it will not print root node value

Comment hidden because of low score. Click to expand.
1
of 1 vote

// 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);
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

But this will violate the order of printing..right?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
}``````

Comment hidden because of low score. Click to expand.
0

Need to take care of terminating condition and double printing of the "vertices".

Comment hidden because of low score. Click to expand.
0

Initial call PrintPerimeter(root,true,true)

Comment hidden because of low score. Click to expand.
0

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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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...)

Comment hidden because of low score. Click to expand.
0

Correction - I am a CS *teacher*...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0

``````your code doesn't work for the following tree. output should be 20 8 4 10 14 12
20
/
8
/     \
4        12
/     \
10     14``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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);
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 "";
// Print left perimeter except the leaf node
{
}

// 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
ArrayList<Tree> list = new ArrayList<Tree>();
{
}
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);
}``````

Comment hidden because of low score. Click to expand.
0

There a few silly errors:
1. ArrayList is of type Integer
2. while printing right perimeter
I just run it, works fine.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Name:

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

### Books

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

### 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.