Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
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));
}
This the best i could think of iterative approach
static int binaryLevelnonRec(Tree head){
if(head==null)
return 0;
LinkedList<Tree> stack1 = new LinkedList<Tree>();
head.depth =1;
stack1.push(head);
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;
}
typo error. pushed leftChild twice :)
stack1.push(current.leftChild);
stack1.push(current.rightChild);
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;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(node);
q.add(delimeter);
while (!q.isEmpty()) {
temp = q.remove();
if (temp == delimeter) {
level += 1;
q.add(delimeter);
continue;
}
if (temp.left != null && temp.right != null) {
if (temp.left != null)
q.add(temp.left);
if(temp.right != null)
q.add(temp.right);
} else {
break;
}
}
System.out.println("At level " + level + " the Tree is balanced.");
}
It is the working code.. Please check..:)
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.
I write this code in eclipse, It can work...
public static boolean Whether_Balance(BinaryTreeNode head){
if(check_process(head,1)!=-1){
return true;
}
return false;
}
public static int check_process(BinaryTreeNode head,int height){
if((head.leftchild==null)&&(head.rightchild==null)){
return height;
}
else if((head.leftchild!=null)&&(head.rightchild!=null)){
int height_left=check_process(head.leftchild,height+1);
int height_right=check_process(head.rightchild,height+1);
if((height_left==-1)||(height_right==-1)){
return -1;
}
else if(height_left!=height_right){
return -1;
}
else
return height_left;
}
else
return -1;
}
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;
}
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;
}
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;
}
- coderFromHell July 25, 2012recursive: 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; }