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+" ");

	}

- amazon engineer May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- arun_lisieux May 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- arun_lisieux May 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anon August 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Prav August 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if the tree is

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

should 4 be printed or not..?

- Prav August 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- poorvisha April 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- poorvisha April 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- poorvisha April 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- poorvisha April 08, 2014 | Flag
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>();
		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;
		}
	}

- amazon engineer May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ravi Chandra March 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ravi Chandra March 11, 2015 | Flag
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);
			}
		}
	}
}

- googlybhai May 08, 2013 | Flag Reply
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)

- Epic_coder May 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Razz May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pradeep May 11, 2013 | Flag
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);
}

- SkyClouds May 06, 2013 | Flag Reply
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.

- go4gold May 07, 2013 | Flag Reply
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 
}

- __Joker May 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- __Joker May 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Initial call PrintPerimeter(root,true,true)

- __Joker May 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SK June 06, 2013 | Flag
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);
}

- Sriramulu Appana May 10, 2013 | Flag Reply
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);

        }

- Pradeep May 11, 2013 | Flag Reply
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...)

- Yossi Yaron May 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Yossi Yaron May 17, 2013 | Flag
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);
}

- RD83 May 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Himanshu July 14, 2013 | Flag
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

- Yossi Yaron May 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- RD83 May 18, 2013 | Flag
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);
			}
		}
	}
}

- Anonymous May 24, 2013 | Flag Reply
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);
}

- Sarthak Mall June 02, 2013 | Flag Reply
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");
}

- SK June 06, 2013 | Flag Reply
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;
                }
            }

}

- jinzha June 16, 2013 | Flag Reply
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;
		}

}

- Anonymous June 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- singh.chakresh August 09, 2013 | Flag Reply
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);

}

- sd November 13, 2013 | Flag Reply
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);
}

- Subhadip Bhattacharya February 25, 2014 | Flag Reply
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

- Subhadip Bhattacharya February 25, 2014 | Flag Reply
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 "";
	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);
	}

- Avsa April 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Avsa April 08, 2014 | Flag
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);
}

- AG April 27, 2016 | Flag Reply


Add a Comment
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.

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