## Amazon Interview Question Software Engineer / Developers

• 0

Given a Binary tree,find the level at which the tree is complete.Complete Binary tree-All leaves should be at same level and every internal node should have two children.
Asked to write both Recursive and iterative code.

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
7
of 9 vote

``````recursive:
checkLevel(node t, int level){
if(t.left != null && t.right != null){
level ++;
return min(checkLevel(t.left,level),checkLevel(t.right,level));
}
else
return level;
}``````

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

Actually there is no need for the level parameter :

``````int complete (node root) {
if(root == null)
return -1;
else
return 1 + Math.min(complete(root.left), complete(root.right));
}``````

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

The algorithm is awesome!

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

This the best i could think of iterative approach

``````static int binaryLevelnonRec(Tree head){
return 0;
int maxCompleteDepth = -1;
while(!stack1.isEmpty()){
Tree current = stack1.pop();
int currDepth = current.depth;
if(maxCompleteDepth !=-1 && maxCompleteDepth<currDepth)
continue;
if(current.leftChild!=null && current.rightChild!=null){
current.leftChild.depth = currDepth+1;
current.rightChild.depth = currDepth+1;
stack1.push(current.leftChild);
stack1.push(current.leftChild);
} else
maxCompleteDepth = currDepth;
}
return maxCompleteDepth;
}``````

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

typo error. pushed leftChild twice :)

``````stack1.push(current.leftChild);
stack1.push(current.rightChild);``````

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

why maxCompleteDepth<currDepth check in if(maxCompleteDepth !=-1 && maxCompleteDepth<currDepth) is necessary?
Because, once maxCompleteDepth has become != -1, other elements in the stack not be verified for the completeness check.
Pls correct me if I'm wrong!

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

``````public static void printTheLevelAtWhichTheBinaryTreeIsComplete(TreeNode node) {

if (node == null) {
System.out.println("The tree is empty.");
System.out.println("-1");
}
int level = 0;
TreeNode delimeter = new TreeNode(-1);
TreeNode temp = null;

while (!q.isEmpty()) {
temp = q.remove();
if (temp == delimeter) {
level += 1;
continue;
}
if (temp.left != null && temp.right != null) {
if (temp.left != null)
if(temp.right != null)
} else {
break;
}

}
System.out.println("At level " + level + " the Tree is balanced.");
}``````

It is the working code.. Please check..:)

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

1. Init completeLevel to 0
2. Start level order traversal (This can be done either by maintaining a delimeter for each level in the queue or by two queue method.)
3 Initialize a flag - isComplete to true.
4. Check for existence of both children for all nodes of current level
5. Break whenever we find isComplete to be false.
6. At completion of level, switch to next level and increment completeLevel.

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

I write this code in eclipse, It can work...

return true;
}
return false;
}
public static int check_process(BinaryTreeNode head,int height){
return height;
}
if((height_left==-1)||(height_right==-1)){
return -1;
}
else if(height_left!=height_right){
return -1;
}
else
return height_left;

}
else
return -1;

}

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

java recursive code

``````static int binaryLevelRec(Tree head){
return 0;
else
}``````

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

Try using BFS for iteration

int findlevel (node root)
{
//using BFS
int level = 0;
Queue Q;

Q.insert(root);

//iterate till the Q is empty
While(!Q.isempty())
{
//For all the nodes of a level make sure if both the nodes are present.
int i = 2*level;
while(i>=0)
{
node n = Q.delete();
if(n.left != null && n.right != null)
{
Q.insert(n.left);
Q.insert(n.right);
}
else
{
break;
}
i--;
}

if(i >=0)
{
break;
}
else
{
level ++
}
}
return level;
}

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

non recursive:
adding all the nodes at each level in a stack and checking the length of the stack.
If its 2 to the power level, at all levels ,we get a complete binary tree.

bool iterativ_check(node* root)
{
stack<node*> st1; // can also take qeue
st1.push(root);
while(st1.size!=0)
{ stack<node*>st2(st1);
st1.clear();
whille(st2.size!=0)
{ node* n1=st2.pop();
if(n1->left!=Null&&n2->rite!=NULL)
{
st1.push(st1[i].left)
st1.push(st1[i].rite)
st2.pop();
}
}
if(st1.size!=Math.power(count,2);
break;
}

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

Iterative

``````private static int fnIterative(Node root) {
int level = 1;
Queue<Node> q1 = new Queue<Node>(10);
Node marker = new Node(999);
q1.insert(root);
q1.insert(marker);
while (!q1.isEmpty()) {
Node curr = q1.delete();
if (curr.left == null || curr.right == null)
break;
else {
q1.insert(curr.left);
q1.insert(curr.right);
}
Node isMarker = q1.peek();
if (isMarker == marker) {
q1.delete();
if (2 * level != q1.size()) {
break;
}
q1.insert(marker);
level++;
}
}
return level;

}``````

Recursive

``````private static int fnrecursive(Node root, int level) {
if (root == null) return -1;
int l = fnrecursive(root.left, level + 1);
int r = fnrecursive(root.right, level + 1);
if (l > 0 && r > 0) {
return l < r ? l : r;
}
return level;

}``````

Comment hidden because of low score. Click to expand.

Name:

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

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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