## Adobe Interview Question

Computer Scientists**Country:**India

**Interview Type:**In-Person

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

geeksforgeeks.org/archives/23796

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.

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.

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

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)

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

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)

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

- atul gupta July 17, 2012