Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Algorithm :
-find depth of each node recursively
-set a variable with depth of first leaf (when traversing)
- if a node is a leaf ,check its depth value with the previously set value
- if all the leaves obey , all leaves are at same level ,
- if any case doesn't obey return -1 breaking recursion. so when -1 is returned by fn then its imperfect , if 0 then all leaves are at same level.
here is the code:
int depth(node *t, int d, int depth)
{
if(!(t->left) && !(t->right)) // this is the leaf
{
if(first==true)// first leaf node
{
first=false;
depth=d;
}
else
{
if(d!=depth)
return -1;
}
return 0;
}
else
{
if(depth(t->left,d+1,depth)==0 && depth(t->right,d+1,depth)==0)
return 0;
else
return -1;
}
}
bool check(Tree *root,int currlevel,int *prevLeaflevel)
{
if(currlevel > prevLeaflevel && prevLeafLevel > 0)
{
return 0;
}
if(root->left == NULL && root->right == NULL)
{
// If leaf node check then check the previous leaf level
if(*prevLeaflevel == 0)
{
// If this is the first leaf
*prevLeaflevel = currlevel;
}
if(currlevel == prevLeaflevel)
{
return 1;
}
else
{
return 0;
}
}
bool b1 = 1;
bool b2 = 1;
if(root->left != NULL)
{
b1 = check(root->left,currlevel+1,&prevLeafLevel);
}
if(b1 && root->right != NULL)
{
b2 = check(root->right,currlevel+1,&prevLeafLevel);
}
return(b1 & b2);
}
Call :
prevleafLevel = 0;
check(root,0,&prevleafLevel);
For the non-recursive version, we can perform the level-order traversal of the tree and add extra conditions that checks for the leavesi.e.,
level=0;
prev=0;
cur=0;
next=0;
queue<bst*>q;
q.push(b);
cur++;
while(!q.empty())
{
b=q.front();
cur--;
q.pop();
if(b->lc!=NULL && b->rc!=NULL)
{
level++;
q.push(b->lc);
next++;
}
else if(b->rc!=NULL)
{
level++;
q.push(b->rc);
next++;
}
else if(b->rc!=NULL)
{
level++;
q.push(b->rc);
next++;
}
else
{
if(prev==0)
prev=level;
else if(prev!=level)
return 0;
}
if(!cur)
{
cur=next;
next=0;
}
}
return 1;
// p4.cpp : main project file.
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *left;
struct node* right;
};
int cnt=0;
struct node* newnode(int data);
void display(struct node* head);
int height(struct node* head);
void printlevel(struct node* head);
void print(struct node* head,int level);
using namespace System;
int main(array<System::String ^> ^args)
{
struct node* head = NULL;
head = newnode(0);
head->left = newnode(2);
head->right = newnode(3);
head->left->right = newnode(4);
head->left->right->right = newnode(7);
head->left->left = newnode(5);
head->left->left->left = newnode(8);
head->right->right = newnode(-4);
head->right->right->right = newnode(-7);
head->right->left = newnode(-5);
head->right->left->left = newnode(-8);
display(head);
printf("\n");
printlevel(head);
return 0;
}
void printlevel(struct node* head)
{
int h = 0,i;
h = height(head);
printf("heaight of tree is %d\n",h);
for(i =h ; i > 0 ; i--)
{
cnt = 0;
print(head,i);
printf("\n");
printf(" count was %d\n",cnt);
}
}
void print(struct node* head,int level)
{
if( head == NULL)
{
return;
}
if( level == 1 )
{
cnt++;
printf("%d ",head->data);
return;
}
else if( level > 1 )
{
print(head->left,level-1);
print(head->right,level-1);
}
return ;
}
int height(struct node* head)
{
int l,r;
if(head == NULL)
return 0;
else
{
l = height(head->left);
r = height(head->right);
if(l > r)
{
return l+1;
}
else
{
return r+1;
}
}
}
struct node* newnode(int data)
{
struct node *temp = NULL;
temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void display(struct node* head)
{
if(head == NULL)
return;
else
{
display(head->left);
printf("%d->",head->data);
display(head->right);
}
}
public static int checkHeight(TreeNode root){
if(root==null){
return 0;
}
//check if left is balanced
int leftHeight = checkHeight(root.leftChild());
if(leftHeight==-1){
return -1;
}
//check if right is balanced
int rightHeight = checkHeight(root.rightChild());
if(rightHeight==-1){
return -1;
}
//checks if the current TreeNode is balanced
int height = leftHeight - rightHeight;
System.out.println(height);
if(Math.abs(height)>1){
return -1;
}else{
return Math.max(leftHeight, rightHeight)+1;
}
}
I have defined a recursive algorithm which can be easily modified for non recursive
void findBalanced(){
int result=findSameHeight(root);
if(result==-1)
printf("not all at same hright");
if(result > = 0)
printf("ALL AT SAME HEIGHT")
}
int findSameHeight(String *node)
{
if(node == null)
return 0;
else{
heightLeft=findSameHeight(node.left);
heightRight= findSameheight(node.right);
if(heightLeft==-1)
return -1;
if(heightRight==-1)
return -1
if(heightRight!=heightLeft)
return -1
return 1+heightLeft+heightRight;
}
}
protected:
int checkLevel(Node* node)
{
if( node == null )
{
return 0;
}
if( node && node->left == null && node->right == null )
{
return 1;
}else{
return 1 + max( checkLevel(node->left), checkLevel(node->right));
}
}
public:
bool checkIfAllLeafSameLevel()
{
return( checkLevel(root->left) == checkLevel(root->right) );
}
Recursive:
int check (Node x)
{
if (x==nil) return 0;
if( (N=check(x.left) ) == check(x.right) ) return N;
return -1;
}
Note: returns -1 on false, >=0 on true (num levels)
void checkLeafLevel(Node* n, std::list<int>& leafLevel, int level)
{
if( n == 0 )
{
return;
}
if( n->left == 0 && n->right == 0 )
{
printf("leaf leavel:%d v:%d\n", level, n->value);
leafLevel.push_front(level);
}else{
checkLeafLevel(n->left, leafLevel, level+1);
checkLeafLevel(n->right, leafLevel, level+1);
}
}
bool isAllLeafsInSameLevel()
{
list<int> leafLevel;
list<int>::iterator leafLevelItr;
checkLeafLevel(root, leafLevel, 0);
int first = *leafLevel.begin();
int size = leafLevel.size();
int sum = 0;
for( leafLevelItr = leafLevel.begin(); leafLevelItr != leafLevel.end(); leafLevelItr++ )
{
sum += *leafLevelItr;
}
return (first == sum/size);
}
C++ Code:
struct Node{
int value;
Node* left;
Node* right;
};
//1. Recursively
bool checkLeafLevel(const Node* p, int level, int& leaf_level)
{
if(!p->left && !p->right){//p is a leaf
if(leaf_level < 0) leaf_level = level;
return level == leaf_level;
}
else{ //p is not a leaf
if(p->left && !checkLeafLevel(p->left, level+1, leaf_level) ||
p->right && !checkLeafLevel(p->right, level+1, leaf_level)) return false;
return true;
}
}
bool areLeavesAtSameLevel(const Node* root)
{
if(root == NULL) return true;
int leave_level = -1;
return checkLeafLevel(root, 1, leave_level);
}
//2. Non-recursively
bool areLeavesAtSameLevel(const Node* root)
{
if(root == NULL) return true;
const Node* p;
queue<const Node*> q;
q.push(root);
int i, level_count, leaves;
while(!q.empty()){
leaves = 0;
for(i = 0, level_count = q.size(); i < level_count; ++i){
p = q.front();
if(!p->left && !p->right) ++leaves;
else{
if(p->left) q.push(p->left);
if(p->right) q.push(p->right);
}
}
if(leaves > 0 && leaves < level_count) return false;
}
return true;
}
I didn't test them. Hope they can work.
def are_all_leaves_at_same_level(root, l):
if root:
left_height, is_balance_left = are_all_leaves_at_same_level(root.left, l + 1)
right_height, is_balance_right = are_all_leaves_at_same_level(root.right, l + 1)
if not (is_balance_left and is_balance_right):
return -1, False
return (left_height, True) if left_height == right_height else (-1, False)
return l, True
See my solution i have posted on geeks for geeks
i have simplified solution in two parts
1. get any leaf node level
2. compare this level with any of leaf node, if any of leaf node in tree is not having same level then all leaf are not present at same level.
class Level {
int level = 0;
boolean atNotSameLevel = false;
}
class GfG
{
Level level = new Level();
boolean check(Node root)
{
// Your code here
getFirstLeafLevel(root, 1);
// level.level = deepestLeafLevel;
// System.out.println("getFirstLeafLevel "+level.level);
leafAtSameLevel(root, level, 1);
return !level.atNotSameLevel;
}
private void leafAtSameLevel(Node root, Level level, int lvl) {
// base case
if(root == null) {
return;
}
// System.out.println(" data "+root.data +" lvl "+lvl);
if(root.left == null && root.right == null && level.level != lvl) {
level.atNotSameLevel = true;
return;
}
leafAtSameLevel(root.right, level, lvl+1);
leafAtSameLevel(root.left, level, lvl+1);
}
private void getFirstLeafLevel(Node root, int l) {
if(root == null) {
return;
}
if(root.left == null && root.right == null) {
level.level = l;
return;
}
// System.out.println("data "+root.data);
getFirstLeafLevel(root.left, l+1);
getFirstLeafLevel(root.right, l+1);
}
}
My Solution-
class Level {
int level = 0;
boolean atNotSameLevel = false;
}
class GfG
{
Level level = new Level();
boolean check(Node root)
{
// Your code here
getFirstLeafLevel(root, 1);
// level.level = deepestLeafLevel;
// System.out.println("getFirstLeafLevel "+level.level);
leafAtSameLevel(root, level, 1);
return !level.atNotSameLevel;
}
private void leafAtSameLevel(Node root, Level level, int lvl) {
// base case
if(root == null) {
return;
}
// System.out.println(" data "+root.data +" lvl "+lvl);
if(root.left == null && root.right == null && level.level != lvl) {
level.atNotSameLevel = true;
return;
}
leafAtSameLevel(root.right, level, lvl+1);
leafAtSameLevel(root.left, level, lvl+1);
}
private void getFirstLeafLevel(Node root, int l) {
if(root == null) {
return;
}
if(root.left == null && root.right == null) {
level.level = l;
return;
}
// System.out.println("data "+root.data);
getFirstLeafLevel(root.left, l+1);
getFirstLeafLevel(root.right, l+1);
}
}
public void printLeaves(Queue<BinaryNode<T>> queue) {
if (queue.size() == 0)
return;
BinaryNode<T> root = queue.poll();
if (root.getLeft() == null && root.getRight() == null) {
System.out.print(root.getData() + "\t");
}
if(root.getLeft()!=null) queue.add(root.getLeft());
if(root.getRight()!=null) queue.add(root.getRight());
printLeaves(queue);
}
public void printLeaves() {
BinaryNode<T> root = this.getRoot();
Queue<BinaryNode<T>> queue=new LinkedList<BinaryNode<T>>();
queue.add(root);
while(!queue.isEmpty()) {
root = queue.poll();
if(root.getLeft()==null && root.getRight()==null) System.out.print(root.getData() + "\t");
if(root.getLeft()!=null) queue.add(root.getLeft());
if(root.getRight()!=null) queue.add(root.getRight());
}
}
Sorry i didn't got the question
Non Recursive version of the code
public boolean checkHeightOfLeaves() {
int count = 0, h3 = 0;
BinaryNode<T> root = this.getRoot();
Queue<BinaryNode<T>> queue = new LinkedList<BinaryNode<T>>();
queue.add(root);
int height = 0;
while (!queue.isEmpty()) {
height++;
count = queue.size();
while (count > 0) {
root = queue.poll();
if (root.getLeft() == null && root.getRight() == null) {
if (h3 == 0)
h3 = height;
else {
if (height != h3) {
return false;
}
}
}
if (root.getLeft() != null)
queue.add(root.getLeft());
if (root.getRight() != null)
queue.add(root.getRight());
count--;
}
}
return true;
}
Recursive One
public boolean checkHeightOfLeaves(Queue<BinaryNode<T>> queue, int height, int new_height) {
if (queue.size() == 0)
return true;
new_height++;
boolean b = false;
int count = queue.size();
while (count > 0) {
BinaryNode<T> root = queue.poll();
if (root.getLeft() == null && root.getRight() == null) {
if (height == 0)
height = new_height;
if (height != new_height)
return false;
}
if (root.getLeft() != null)
queue.add(root.getLeft());
if (root.getRight() != null)
queue.add(root.getRight());
count--;
}
return checkHeightOfLeaves(queue, height, new_height);
}
- Anonymous September 26, 2013bool IsLeaf(Node node) { if(node.left==null && node.right==null) return true; return false; } bool CheckBalance(List<Node> l) { bool collectionHasLeaf=false; List<Node> listOfChildren=new List<Node>(); foreach(Node n in l) { if(IsLeaf(n)){ collectionHasLeaf=true}; else { if(n.left!=null){listOfChildren.Add(n.left);} if(n.right!=null){listOfChildren.Add(n.right)}; } } if(collectionHasLeaf) { if(listOfChildren.Count>0) return false; return true; } return CheckBalance(listOfChildren); } Public bool CheckBalance(Node head) { List<Node> l=new List<Node>(); l.Add(head); return CheckBalance(l); }