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