## Adobe Interview Question for Computer Scientists

Country: India
Interview Type: In-Person

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

is it like we need to calculate the numbers of the leaf nodes in the tree(binary or BST)?????

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

addition to that length of left most branch +right most branch...

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

I think the question is for traversing the boundary of a tree.

geeksforgeeks.org/archives/23796

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

@Psycho Does algo at geeksforgeeks work for below tree?

``````1
2
3                   4
5        6         7       8
9    10``````

i think it will not print right side boundary 4, 8..Please respond.

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

Please explain it a little further. If possible give a sample example

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

Is a real tree or binary tree or n-ary tree, can you explain. I thought it is a brain teaser first that you move around a real tree and find its circumference or are you talking about binary tree

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

Circumference of a tree is basically all outermost nodes. The extreme left and right paths and all leaves. So

``````1
2     3
4 5   6  7
8 9 0 1 2 4``````

will have circumference -> 1,2,4,8,9,0,1,2,4,7,3.

Do a simple level wise traversal using a queue and except for the last level, print only first and last node at each level.

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

cud u be more specific? what if every level has leafs?

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

Does not matter. Imagine a circumference of a tree. Like a border. Your level wise traversal ensure that you always have leftmost and rightmost node which is whats required.

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

in given example if we remove 4 and 8 elements than will 5 be included on circumference of tree ,in this case 5 is neither leftmost element nor leaf ,but it is leftmost element at its level .........so will it be included thanx

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

Your solution will work only for complete tree.
It wont work for the case:
10
4 3
5 6 7 9
/
15

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

Do inorder traversal
perimeter of tree = (depth of first left child -1) + (no of children) + (depth of right most child -2)

depth of first left child -1: this will count the left boundary element and -1 exclude the child.
depth of right most child -2: count the elements on right boundary and -2 exclude right most child and root (root has already counted while traversing left)

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

naveen i dont think question meant any calculation we just had to print the circumference

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

see i have tried to write an algo for this

my idea is i have divided the tree nodes into 5 modes 1. either node is a root 2. node is a leaf node 3. node lies in the left circumference wrt root 4. node lies in the right circumference 5. nodes are intermediate nodes and based on that i have written a simple level wise traversal

``````function printCircumference(Node node, Mode mode){
if(isLeafNode(node))
print node.value;
else if(mode == root)
{
print node.value
printCircumference(node.leftChild, left)
printCircumference(node.rightChild, rigt)
}
else if(mode == left)
{
print node.value
printCircumference(node.leftChild, left)
printCircumference(node.rightChild, intermediate)

}
else if(mode == right)
{
print node.value
printCircumference(node.leftChild, intermediate)
printCircumference(node.rightChild, right)
}
else{
//intermediate nodes
printCircumference(node.left, intermediate)
printCircumference(node.right, intermediate)

}

}``````

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

Sorry there is a problem in the above algo havent taken the case if tree is nt complete binary tree. In that case for each node need to check whether it has 2 or 1 child node(s)

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

There is minor code change needed :

Idea is to do preOrder for mode=left and postOrder for mode=right

the loop is corrected now:

``````else if(mode == right)
{
printCircumference(node.leftChild, intermediate)
printCircumference(node.rightChild, right)
print node.value
}``````

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

Please let me know if the sol has some flaw.

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

a
b c
d e f
g h

Above tree will give output
abdeghca
it will skip f

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.