Amazon Interview Question SDE1s
Country: India
@Loler: Is not the same approach I mentioned earlier.Just wanted to know if there is any difference?
@aka: It is the same, but you seem to have skipped the implementation details of how to maintain the level information etc, which is not hard, but also not trivial. Also, I wanted to mention the drawbacks of DFS, and added an implementation.
btw, if one chooses to use BFS, the solutions will all be quite similar. Don't you think? :-)
I think this problem can be solved without using recursive and within linear time. This problem is same as the problem that a given binary tree is whether a complete binary tree or not. we can do level traversal of the binary tree, and before traverse a level we compute the expected nodes than we visit at current level by the level previous, that means double the count of nodes of previous level, then when we visit current level and keep a count. After traverse current level, we compare current nodes count and expected, if they are equal,then we set expected = count * 2, then do traverse of next level. Here is my code:
#include<iostream>
#include<vector>
using namespace std;
typedef struct tree_node_s {
int value;
struct tree_node_s* lchild;
struct tree_node_s* rchild;
}tree_node_t;
tree_node_t* createNode(int value) {
tree_node_t* node = (tree_node_t*)malloc(sizeof(tree_node_t));
node->value = value;
node->lchild = NULL;
node->rchild = NULL;
return node;
}
bool is_complete_bin_tree(tree_node_t* root) {
int cur = 0;
int last = 0;
int count = 0;
int node_has_child = 0;
int node_non_child = 0;
int expected = 0;
if (NULL == root)
return true;
vector<tree_node_t*> vec;
tree_node_t* node = NULL;
vec.push_back(root);
while (cur < vec.size()) {
last = vec.size();
count = 0;
node_has_child = 0;
node_non_child = 0;
while (cur < last) {
node = vec[cur];
cout << node->value << " ";
cur++;
count++;
if (node->lchild || node->rchild) {
node_has_child++;
} else {
node_non_child++;
}
if (node->lchild)
vec.push_back(node->lchild);
if (node->rchild)
vec.push_back(node->rchild);
}
if (node_non_child > 0 && node_non_child < count)
return false;
cout << endl;
if (count >= expected) {
expected = node_has_child;
} else {
return false;
}
}
return true;
}
int main(int argc, char* argv[]) {
tree_node_t* root = createNode(1);
root->lchild = createNode(2);
root->rchild = createNode(3);
root->lchild->lchild = createNode(4);
root->lchild->rchild = createNode(5);
root->rchild->lchild = createNode(6);
root->rchild->rchild = createNode(7);
if (is_complete_bin_tree(root))
cout << "yes" << endl;
else
cout << "non" << endl;
cin.get();
return 0;
}
It will fail if the tree is
10
8 12
7 14
It expects 4 nodes at level 2. But in this tree all leaves are at same level.
Just minor modifications required ..
public static boolean checkTreeLevel(TreeNode root) {
TreeLevelResult result = checkTreeLevel(root, 0);
return result.value;
}
private static TreeLevelResult checkTreeLevel(TreeNode root, int level) {
if (root == null) return new TreeLevelResult(level, true);
if (root.left == null && root.right == null) return new TreeLevelResult(level, true);
TreeLevelResult left = checkTreeLevel(root.left, level + 1);
if (!left.value) return left;
TreeLevelResult right = checkTreeLevel(root.right, level + 1);
if (!right.value) return right;
if (left.level != right.level) return new TreeLevelResult(Math.max(left.level, right.level), false);
return new TreeLevelResult(left.level, true);
}
public class TreeLevelResult {
public int level;
public boolean value;
public TreeLevelResult(int level, boolean value) {
this.level = level;
this.value = value;
}
}
do level order traversal,then count nodes in each level and varify this count with pow(2,h)
h-:height of tree
4
3 2
1
Start from 4 and add it in a queue.Dequ and add it's children i.e. 3 and 2 in queue.
Again dequ and get 3.Add it's children 1 in queue.Dequeu 2 and here you notice that it's children doesn't exist.Mark this level.Deque 1 and you see that it doesn't have any children and you also notice that the level is not save as the the one you marked so return 0(boolean value).
Basically do bfs and note down the level when you find out that a particular node doesn't have any children and compare with all the leaf node you find along the bfs way.
do a Depth first search with "level" for the root element as '0'. Each node's "level" is 1 added to the parent's level. Each node receives a tuple of the (min leaf level, max leaf level) from the left and right sub-tree and evaluates its own (min, max) tuple. Once you return to the root, you compare min and max. following is the code in python:
nodes = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
left_child = { 'a' : 'b',
'b' : 'd',
'c' : 'f'
}
right_child = { 'a' : 'c',
'b' : 'e',
'c' : 'g'
}
def DFS(node, level):
if (node not in left_child) and (node not in right_child):
print "leaf node: " + node + "\t level: " + str(level)
return (level, level) #returning (max leaf level, min leaf level)
if node in left_child:
max_left, min_left = DFS(left_child[node], level+1)
if node in right_child:
max_right, min_right = DFS(right_child[node], level+1)
if max_left is None:
maxx = max_right
elif max_right is None:
maxx = max_left
else:
maxx = max(max_right, max_left)
if min_left is None:
minx = min_right
elif min_right is None:
minx = min_left
else:
minx = min(min_right, min_left)
return (minx,maxx)
def equal_leaves():
minx, maxx = DFS('a',0)
return minx == maxx
### MAIN CALL
print equal_leaves()
For each node check if the height of left subtree is same as that of right subtree. If true for all nodes return True otherwise return False.
Using a botton up approach this could be solved in O(n) time and constant space.
This works, but there is an overhead in calculating the height, and this can be avoided. Check my solution below.
Whateva' - If the tree doesn't have a right subtree, the height of right would be 0 and height of left subtree would be non-zero. That will return False.
thushw - Your solution has a subtle bug. I want you to figure it out.
int is_same_level(Tree* t){
if (!t) return 1; //consider NULL tree as all leaves on one level(0)
if (t->left && !t->right || !t->left &t->right) return 0;
int lv = is_same_level(t->left);
if (!lv) return 0;
return is_same_level(t->right);
}
1
2 3
4 5
consider the above tree .....do the level order traversal..
first place the root in the queue and place a NULL in the queue( this NULL indicates end of the level )..now follow the steps
by consider the above tree. initially the queue is
1 NULL..
1.dequeue the node from the queue..and place all the childrens of that node in the queue..this time the queue is
NULL 2 3 NULL
2.if u found the NULL skip..it..
3.take the another element (that is 2 in this case) place all childrens of 2 in queue ..now the queue is
3 NULL 4 5
4.and next element is 3 we delete that from queue and insert all the children into queue..but 3 has no children..
now my solution is if u found any node with no children.. from there once u found the NULL in the queue , Queue has no more elements other than NULL if it is true the given tree has all leaves at same level other wise the tree has leaves in different levels..
in this case 3 has no children after that u found a NULL and still the queue has some elements..so the given tree has leaves in different levels..
Kindly check following rec soln n let me know if it is not correct
int ifLeavesAtSameLevel(node* root,int level){
if(!root->left && !root->right)
return level;
int l=0,r=0;
if(root->left)
l=ifLeavesAtSameLevel(root->left,level+1);
if(root->right)
r=ifLeavesAtSameLevel(root->right,level+1);
if((l && r && l==r) || (!l && r) || (l && !r))
return (l?l:r);
return 0;
}
int ifSameLevelLeaves(node* root){
if(!root || (!root->left && !root->right))
return 1;
if(root->left && root->right)
return ifLeavesAtSameLevel(root,1);
return 0;
}
Maintain current level and next level. Current level decreases each time you deque and next level increments each time you enqueue -- when this level runs to 0, set this level to next level, then next level to 0. This way, you know exactly how many nodes are there in each level and this can compere if there is an imbalance. Hopefully the code will clarify better:
public boolean checkLeafLevel(Node root) {
if(root == null)
return true;
//Assuming node has left and right both
Queue<Node> q = new LinkedList<Node>();
q.add(root.left);
q.add(root.right);
int thisLevel = 2;
int nextLevel = 0;
while(!q.isEmpty()) {
boolean nodeHasChild = false;
Node node = q.remove();
thisLevel--;
if(node.left != null) {
nodeHasChild = true;
q.add(node.left);
nextLevel++;
}
if(node.right != null) {
nodeHasChild = true;
q.add(node.right);
nextLevel++;
}
if(thisLevel == 0) {
thisLevel = nextLevel;
nextLevel = 0;
}
else if(nodeHasChild && q.peek().right == null && q.peek().left == null)
return false;
}
return true;
}
public static bool isValidBST(Node rootNode)
{
if (rootNode == null)
return true;
else if (rootNode.leftNode == null && rootNode.rightNode == null)
return true;
else if ((rootNode.leftNode != null && rootNode.rightNode == null)
|| (rootNode.rightNode != null && rootNode.leftNode == null))
return false;
else
{
++leftCount;
isValidBST(rootNode.leftNode);
++rightCount;
isValidBST(rootNode.rightNode);
}
return leftCount == rightCount;
}
static void Main(string[] args)
{
#region tree's
//int[] arr = new int[] { 7, 4, 9, 3, 5, 8, 10 };
int[] arr = new int[] { 7, 6, 11, 26, 2, 4, 5 };
foreach (int data in arr) rootNode = addNode(rootNode, data);
searchLeafNode(rootNode);
foreach (int data in leafNodes)
{
count = 0;
getLevelOfEachLeafNode(rootNode, data);
}
if (res.Distinct().Count() == 1)
Console.WriteLine("\n\nthe validity of given bst is {0}", true);
else
Console.WriteLine("\n\nthe validity of given bst is {0}", false);
#endregion
}
static List<int> leafNodes = new List<int>();
static List<int> res = new List<int>();
static int count = 0;
public static void searchLeafNode(Node rootNode)
{
if (rootNode != null)
{
if (rootNode.leftNode == null && rootNode.rightNode == null)
leafNodes.Add(rootNode.data);
else
{
searchLeafNode(rootNode.leftNode);
searchLeafNode(rootNode.rightNode);
}
}
}
public static bool getLevelOfEachLeafNode(Node rootNode, int data)
{
count += 1;
if (rootNode == null)
return true;
else if (rootNode.data == data
&& (rootNode.leftNode == null && rootNode.rightNode == null))
return true;
else
{
if (data < rootNode.data)
{
if (getLevelOfEachLeafNode(rootNode.leftNode, data))
{
if (rootNode.leftNode.data == data)
res.Add(count - 1);
return true;
}
}
if (data > rootNode.data)
{
if (getLevelOfEachLeafNode(rootNode.rightNode, data))
{
if (rootNode.rightNode.data == data)
res.Add(count - 1);
return true;
}
}
}
count -= 1;
return false;
}
The idea is to use BFS while keeping track of the number of nodes in the current level as well as the depth of the current level. If the number of nodes at level i < 2^i AND there are nodes in the next level then we return false.
In the following method, we maintain four variables:
1- nodesToProcessInCurrentLevel keeps track of how how many nodes we have to process in the current level (and when it equals zero, it means that we done processing with the current level)
2- nodesInNextLevel keeps track with the number of nodes in the next level and it's incremented each time we insert a child of any node at the current level
3- nodesInCurrentLevel is the total number of nodes at the current level
4- depth is the depth of the current level
public static boolean checkLeavesAtSameLevel(Node root){
if(root == null) return true;
Queue<Node> queue = new LinkedList<Node>();
int nodesToProcessInCurrentLevel = 1;
int nodesInNextLevel = 0;
int nodesInCurrentLevel = 0;
int depth=0;
queue.add(root);
while(queue.size()>0){
Node node = queue.poll();
nodesInCurrentLevel++; //while polling keep track of the number of processed nodes
nodesToProcessInCurrentLevel--;
if(node.leftNode!=null){
queue.add(node.leftNode);
nodesInNextLevel++; //track the number of nodes of the next level
}
if(node.rightNode != null){
queue.add(node.rightNode);
nodesInNextLevel++;
}
if(nodesToProcessInCurrentLevel==0){
if(nodesInCurrentLevel < Math.pow(2, depth) && nodesInNextLevel>0) return false;
depth++;
nodesToProcessInCurrentLevel=nodesInNextLevel;
nodesInNextLevel=0;
nodesInCurrentLevel=0;
}
}
return true;
}
void levelize(node* root, int level,map<node*,int>& leafVsLevel)
{
if(!root){
return;
}
if(!root->left && !root->right) {
leafVsLevel[root] = level;
return;
}
levelize(root->left,level+1,leafVsLevel);
levelize(root->right,level+1,leafVsLevel);
return;
}
bool samelevel(node* root)
{
if(!root) {
return true;
}
map<node*,int> leafVsLevel;
levelize(root,0, leafVsLevel);
map<node*, int>::iterator it = leafVsLevel.begin();
bool rsl(true);
int prevLevel(-1);
while(it != leafVsLevel.end()) {
int currLevel = it->second;
if(prevLevel == -1) {
prevLevel = currLevel;
}
else if(prevLevel != currLevel) {
rsl = false;
break;
}
it++;
}
leafVsLevel.clear();
return rsl;
}
private static Boolean isBalanced(TreeNode head) {
if (checkBalanced(head) == -1) {
return Boolean.FALSE;
} else {
return Boolean.TRUE;
}
}
private static int checkBalanced(TreeNode head) {
if (head == null) {
return 0;
}
int leftHeight = checkBalanced(head.left);
if(leftHeight==-1)
return leftHeight;
int rigthHeight = checkBalanced(head.right);
if(rigthHeight==-1)
return rigthHeight;
if (leftHeight != rigthHeight) {
return -1;
} else {
return leftHeight+1;
}
}
#include<stdio.h>
#include<stdlib.h>
struct tree
{
int n;
struct tree *left;
struct tree *right;
};
typedef struct tree node;
int is_leaf_at_same_level(node *root,int *i)
{
int leftheight=0,rightheight=0;
if(root != NULL)
{
if(root->left != NULL)
leftheight = 1 + is_leaf_at_same_level(root-> left,i);
if(root->right != NULL)
rightheight = 1 + is_leaf_at_same_level(root-> right,i);
if(root->left == NULL)
leftheight = rightheight;
if(root->right == NULL)
rightheight = leftheight;
if(leftheight==rightheight)
{
*i=1;
return leftheight;//or rightheight
}
*i=0;
return 0;
}
}
node * createTree(node *root,int x)
{
node *p,*q,*nw;
nw=(node *) malloc(sizeof(node));
nw->n=x;
nw->left=NULL;
nw->right=NULL;
if(root==NULL)
{
root=nw;
return root;
}
p=root;
while(p!=NULL)
{ q=p;
if(p->n < x)
p=p->right;
else
p=p->left;
}
if(q->n < x)
q->right=nw;
else
q->left=nw;
return root;
}
void main()
{
int i=0,k,n;
node *root=NULL;
printf("Enter how many nos: \n");
scanf("%d",&k);
while(k!=0)
{ printf("enter no: \n");
scanf("%d",&n);
root=createTree(root,n);
k--;
}
is_leaf_at_same_level(root,&i);
printf("%d\n",i);
}
Before writing the code I would like to clarify that a leaf node must always have 0 children.
I would use recursive postorder traversal as follows:
/*Function returns -1 if all the leaf nodes are NOT at the same level, something else otherwise. A wrapper could be written to map these returned values to bool */
int sameLevel(Node *root){
if(!root) return 0;
int left = sameLevel(root->left);
int right = sameLevel(root->right);
if(left == -1 || right == -1) return -1;
if(left == right) return left+1;
if(left == 0 || right == 0) return (left != 0? left+1:right+1); //This is the case when exactly one of the children of a node is NULL
return -1;
}
Time complexity = O(n)
Space complexity = O(1)
I am writing the complete code here
public static void main(String[] args){
BinaryTree bt = new BinaryTree();
int[] data = {3, 4, 1, 0, 6, 4, 2, 8, 0, 9};
bt.buildTree(data); //here i am building my bst
System.out.println(bt.isSameLevel());
/**How to find in a binary tree, whether all leaves are at same level or not,
* and return a boolean value after identifying this.
*/
public boolean isSameLevel(){
return(isSameLevel(root));
}
private boolean isSameLevel(Node node){
if(node.left == null && node.right == null) return true;
else if(node.left == null || node.right == null) return false;
return isSameLevel(node.left) && isSameLevel(node.right);
}
}
def isleafsamelevel(root):
firstleaflevel = None
if not root:
return False
l = [root]
level = 0
while l:
print ' '.join([str(n.val) for n in l])
nl = []
for n in l:
if n.left:
nl.append(n.left)
if n.right:
nl.append(n.right)
if not n.left and not n.right:
if firstleaflevel is None:
firstleaflevel = level
if level != firstleaflevel:
return False
l = nl
level += 1
return True
public bool samelevel(TreeNode root, int level, int currentlevel)
{
if (root == null)
return true;
if (root.left == null || root.right == null)
{
if (currentlevel != level && currentlevel >= 0)
return false;
currentlevel = level;
}
return samelevel(root.left, level + 1, currentlevel) && samelevel(root.right, level + 1, currentlevel);
}
public bool samelevel(TreeNode root, int level, int currentlevel)
{
if (root == null)
return true;
if (root.left == null || root.right == null)
{
if (currentlevel != level && currentlevel >= 0)
return false;
currentlevel = level;
}
return samelevel(root.left, level + 1, currentlevel) && samelevel(root.right, level + 1, currentlevel);
}
We can determine this by performing Level Order traversal little carefully...
-Check every node that you dequeue -whether it has children or not.
-If not then it must be the first node of that level and all the nodes following it in the queue must not have children then
-else if - any node after this in the queue has children then the leaves can't be on same level.
I tried my best to explain ..still if any doubts feel free to discuss.
1)The main idea of this approach is to do a BFS and check each node.
2)If current node is leaf node then we check for two conditions
2.1)If it is extreme right leaf node of that level, then there shouldn't be any node following.(i.e queue should be empty)
2.2)If it is any other leaf node then we check that any of the following node in that level must also be a leaf node
// Iterative method to check whether all leaf are at same level or not
int samelevelcheck(node *root)
{
// Base Case
if (root == NULL)
return 0;
// Create an empty queue for level order tarversal
queue<node *> q;
q.push(root);
while (1)
{
// nodeCount (queue size) indicates number of nodes at current level.
int nodeCount = q.size();
if (nodeCount == 0)
return 1;
// Dequeue all nodes of current level and Enqueue all
// nodes of next level
while (nodeCount > 0)
{
node *newnode = q.front();
q.pop();
if (newnode->left != NULL)
q.push(newnode->left);
if (newnode->right != NULL)
q.push(newnode->right);
/*if current node is leaf node then we check for two conditions
if((newnode->left== NULL && newnode->right== NULL))
{
//1)If it is extreme right leaf node of that level, then there shouldn't be any node following.(i.e queue should be empty)
if((nodeCount==1 && q.size()>0))
return 0;
//If it is any other leaf node then we check that any of the following node in that level must also be a leaf node
else
{
nodeCount = q.size();
while(nodeCount>0)
{
node *temp = q.front();
q.pop();
if(temp->left||temp->right)
return 0;
nodeCount--;
}
}
}
nodeCount--;
}
}
return 1;
}
1)Simplest way is to do BFS and check every node
2)if current node is leaf node then we check for two conditions
2.1)If it is extreme right leaf node of that level, then there shouldn't be any node following.(i.e queue should be empty)
2.2)If it is any other leaf node then we check that any of the following node in that level must also be a leaf node
int samelevelcheck(node *root)
{
// Base Case
if (root == NULL)
return 0;
queue<node *> q;
// Enqueue Root
q.push(root);
while (1)
{
// nodeCount (queue size) indicates number of nodes at current level.
int nodeCount = q.size();
if (nodeCount == 0)
return 1;
// Dequeue all nodes of current level and Enqueue all
// nodes of next level
while (nodeCount > 0)
{
node *newnode = q.front();
q.pop();
if (newnode->left != NULL)
q.push(newnode->left);
if (newnode->right != NULL)
q.push(newnode->right);
//if current node is leaf node then we check for two conditions
if((newnode->left== NULL && newnode->right== NULL))
{
//1)If it is extreme right leaf node of that level, then there shouldn't be any node following.(i.e queue should be empty)
if((nodeCount==1 && q.size()>0))
return 0;
//If it is any other leaf node then we check that any of the following node in that level must also be a leaf node
else
{
nodeCount = q.size();
while(nodeCount>0)
{
node *temp = q.front();
q.pop();
if(temp->left||temp->right)
return 0;
nodeCount--;
}
}
}
nodeCount--;
}
}
return 1;
}
public boolean isFullTree() {
int depth = 0;
int expectedNodes = (int)Math.pow(2, depth);
Queue<Node> q = new LinkedList<Node>();
q.add(this);
while(!q.isEmpty()) {
if (q.size() != expectedNodes)
return false;
for (int i = 0; i < expectedNodes; i++) {
Node n = q.remove();
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
depth++;
expectedNodes = (int)Math.pow(2, depth);
}
return true;
}
public boolean isFullTree() {
int depth = 0;
int expectedNodes = (int)Math.pow(2, depth);
Queue<Node> q = new LinkedList<Node>();
q.add(this);
while(!q.isEmpty()) {
if (q.size() != expectedNodes)
return false;
for (int i = 0; i < expectedNodes; i++) {
Node n = q.remove();
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
depth++;
expectedNodes = (int)Math.pow(2, depth);
}
return true;
}
public boolean isFullTree() {
int depth = 0;
int expectedNodes = (int)Math.pow(2, depth);
Queue<Node> q = new LinkedList<Node>();
q.add(this);
while(!q.isEmpty()) {
if (q.size() != expectedNodes)
return false;
for (int i = 0; i < expectedNodes; i++) {
Node n = q.remove();
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
depth++;
expectedNodes = (int)Math.pow(2, depth);
}
return true;
}
public boolean isSameLevel(){
return(isSameLevel(root));
}
private boolean isSameLevel(Node node){
if(node.left == null && node.right == null) return true;
else if(node.left == null || node.right == null) return false;
return isSameLevel(node.left) && isSameLevel(node.right);
}
This is incorrect. It is possible that both left and right subtree have all their leaves at the same level and still it's not true for the whole tree.
BFS (breadth first search) is likely the way to go (unless utterly space constrained). DFS (depth first search) could be inefficient. Consider a tree with a million nodes in the left sub-tree, but just one in the right. If you traverse the left subtree first, you will waste a lot of time.
At each level you can count the number of leaves and bailing out as soon as you can tell when the number isn't going to be the same as the number of nodes at that level.
Something like this (haven't tried verifying it etc)
- Loler June 04, 2013bool LeavesAtSameLevel(Tree<T> tree) { Queue <T> queue; if (tree == null || tree.isLeaf()) return true; queue.push(tree); uint expected = 1; // How many at current level we expect uint seen = 0; // How many nodes we have seen at current level. uint queued = 0; // How many we have queued for next level. uint leaves = 0; // How many leaves we have seen at current level. while (queue.hasElements()) { Tree<T> cur = queue.pull(); seen++; if (cur.Left) { queue.push(cur.Left); queued++; } if (cur.Right) { queue.push(cur.Right); queued++; } if (cur.IsLeaf()) { leaves++; } // Seen some leaves, but not the same as the total nodes seen. if (leaves > 0 && seen != leaves) { return false; } if (seen == expected) { // Finished traversing one level. expected = queued; seen = queued = 0; } } return true; }