Microsoft Interview Question
Program Managers1. Firstly, we need to enlist all the leaf nodes and their levels in the tree. In order to do this, do a Level order Traversal on the Tree (using queue) and store all leaf node and their levels into a 2d array (by verifying if the node doesn't have child nodes and maintaining a level variable in the recursive level order traversal).
2. Now that we have 2d array of all leaf nodes and its level, we need to find all array elements, wherein difference of levels is 2 or more. O(n square) time complexity we can find all nodes differing by 2 or more. Any better approach, please share.
The level order traversal in binary tree can be brought about by
void LevelOrderTraversal(Tree myBinTree) {
Queue myQ = new Queue();
Tree myTree = myBinTree;
int level = 0;
while(myTree != null) {
if(myTree.leftChild == null && myTree.rightChild == null)
Insert <myTree, level> into the 2d array
if(myTree.leftChild != null)
myQ.add(myTree.leftChild);
if(myTree.rightChild != null)
myQ.add(myTree.rightChild);
myTree = q.delete(myTree); //deletes the current node and returns the next node in Q
level++;
}
//Have to code the algo to find the nodes differing by >1 levels.
You just making simple things complicated.
Do DFS of tree calucating minimum and maximum depth in parralel. Stop when max - min >= 2.
Solution is O(n) (well, we can do it in n^2, n^3 and so on :) )
@gevorgk: "Depth First Search of Binary tree"... Can you please elaborate on which kind of traversal do you intend to do. A pseudo code/algo would be great.. Didn't actually get it completely...
And how are you enlisting all the leaf nodes which differ by >1 level difference?
gevorgk,
Depth first search won't work. because for nodes which has only one child min-depth will be that from no-child side but there is no leaf there.
I think a good approach would be to traverse Breadth first and keep track of levels by maintaining child count for a level added in queue. check each node while popping it whether it's leaf note down max and min levels of leafs.
you can quit the traversal in middle if question is to find out whether a certain difference of depth for leaves exist in tree
Ok, let me exlplain better. Question says wether there a ANY 2 leaf nodes, which differ by more than 1 level.
We will find the leaf with Min depth, and leaf with max depth. If the deifference is more than 1 - it means that we have at list one such pair. If difference is less than or equal to 1 - it means than there will be no such pairs, because the difference between min and max is largest one.
Guys, How about this. We use a global variable array of size two to keep tracking of min and max depth. Then we recursively DFS this Binary tree (don't forget to count the depth). When we hit the leaf node update min max can check max-min >=2. When it does flag the boolean so that we can eliminate unnecessary search. Then it O(N) in time with a use of O(2) array.
int depth[] = {0,0}; //global variable O(2)
bool check_leaf(Node &n_,int dep)
{
//base case
if(n_.Left == NULL && n_Right == NULL)
{
if(dep > depth[0])
depth[0] = dep;
else if(dep < depth[1])
depth[1] = dep;
if(depth[0] - depth[1] >= 2)
return true;
else
return false;
}else
{
if(n_.Left != NULL) //Not a leaf node
if(check_leaf(n_.left,dep++))
return true; //stop unnecessary search
if(n_.Right != NULL) //Not a leaf node
if(check_leaf(n_.left,dep++));
return true; //stop unnecessary search
return false;
}
}
Another idea is to find the height of the left tree, find the height of the right tree. If the difference is more than 1, we return an error. The pseudo code will be some thing of this sort.
// Function return -1 if the difference is more than 1 level
// Function returns height of the tree other wise
// Assumptions : a properly constructed binary tree
int height(struct node** head)
{
// If head is equal to 0 return 0
//else t1 holds the height of the left tree t2 holds the height of the right tree
// if either of them is -1 that means some where down below there exits a sub tree with difference of more than 1 level. return -1
// if the difference is 0 or 1. then return the max height between either of the sub trees + 1
// else if the difference is 2 , return -1
}
int maxormin (int a, int b, int choice)
{
if (choice==0) return (a>b)?a:b;
if (choice==1) return (a<b)?a:b;
}
void height(node *root , int choice)
{
int maxht, minht;
if(root==NULL) return 0;
maxht= 1+maxormin(height(root->rlink),height(root->llink),0);
minht = 1+maxormin(height(root->rlink),height(root->llink),1)
if(maxht-minht > 1)
{
printf("yes > 1");
exit(0);
}
}
private void TraverseWithHeight (Node* t, int * min, int * max, int * height)
{
if(t == null) return;
if(t->left == NULL && t->Right == null)
{
If(height < min) min = height;
If(height > max) max = height;
Height --;
return; //leaf
}
Else
{
Height ++;
if (t->left != NULL)
TraverseWithHeight( t->left , min, max, height);
else
TraverseWithHeight( t->right , min, max, height);
}
}
Bool tree_diff_level(node *root)
{
Min = Min_height(root);
Max = Max_height(root);
If(max > min)
Return(true);
Else
Return(false);
}
Min_height(node *root)
{
If(root == NULL)
Return(0);
Return(min(Min_heigh(root->left), Min_height (root->right)),+1);
}
Max_height(node *root)
{
If(root == NULL)
Return(0);
Return(max(Max_heigh(root->left), Max_height (root->right)),+1);
}
int checkDepth (Node *node)
{
if (node == 0)
return 0;
int left_len, right_len, difference;
left_len = right_len = difference = 0;
left_len = checkDepth (node->left);
right_len = checkDepth (node->right);
difference = abs (left_len - right_len);
if (difference > 1)
{
printf ("The tree has a difference of more than one");
exit (0);
}
else
return (MAX(left_len, right_len)+1);
}
public static boolean check(Node root){
return check(root,0) <= 1;
}
private static int check(Node node,int level){
if(node == null)
return level;
if(node.left != null && node.right != null)
return level;
int left = check(node.left,level+1);
int right = check(node.right,level+1);
return Math.abs(left-right);
}
public static boolean check(Node root){
return check(root,0) <= 1;
}
private static int check(Node node,int level){
if(node == null)
return level;
if(node.left == null && node.right == null)
return level;
int left = check(node.left,level+1);
int right = check(node.right,level+1);
return Math.abs(left-right);
}
Traverse each node using BFS
If CurrentNode.HasChildren() == false then // leaf node
Add_Node_To_Array_After_Level_Check(CurrentNode)
End If
Print all elements in the NodeList as they have a level difference more than 1
function Add_Node_To_Array_After_Level_Check(Node)
{
for(index = NodeList.Length-1 to 0)
{
if(Node.Level - NodeList[index].Level>1)
{
NodeList.Add(Node);
break;
}
}
}
Can be done in Scala easily:
object scratchie2 {
class Tree(val left: Tree, val right: Tree)
val root1 = new Tree(null, null) //> root1 : com.test.scratchie2.Tree = com.test.scratchie2$Tree@5efd2ebd
val root2 = new Tree(new Tree(null, null), null)//> root2 : com.test.scratchie2.Tree = com.test.scratchie2$Tree@5858ba4b
val root = new Tree(new Tree(null, null), new Tree(null, new Tree(new Tree(null, null), null)))
//> root : com.test.scratchie2.Tree = com.test.scratchie2$Tree@292ebf3d
def isBalanced(tree: Tree): Boolean = {
if (tree.left == null && tree.right == null)
true
else if (tree.left != null && tree.right != null) {
isBalanced(tree.left) && isBalanced(tree.right)
} else if (tree.left != null && tree.right == null) {
tree.left.left == null && tree.left.right == null
} else {
tree.right.left == null && tree.right.right == null
}
} //> isBalanced: (tree: com.test.scratchie2.Tree)Boolean
isBalanced(root1) //> res0: Boolean = true
isBalanced(root2) //> res1: Boolean = true
isBalanced(root) //> res2: Boolean = false
}
Here is just the code, use it in a worksheet or a class:
object scratchie2 {
class Tree(val left: Tree, val right: Tree)
def isBalanced(tree: Tree): Boolean = {
if (tree.left == null && tree.right == null)
true
else if (tree.left != null && tree.right != null) {
isBalanced(tree.left) && isBalanced(tree.right)
} else if (tree.left != null && tree.right == null) {
tree.left.left == null && tree.left.right == null
} else {
tree.right.left == null && tree.right.right == null
}
}
}
Here's the complete code
- Amit Priyadarshi August 16, 2010int maxDepth(Tree* root)
{
if (root == NULL) return 0;
else
{
int ldepth = maxDepth(root->left) + 1;
int rDepth = maxDEpth(root->right) + 1;
return ((ldepth>rDepth) ? ldepth:rdepth);
}
}
int minDepth(Tree* root)
{
if (root == NULL) return 0;
else
{
int ldepth = minDepth(root->left) + 1;
int rDepth = minDEpth(root->right) + 1;
return ((ldepth>rDepth) ? rdepth:ldepth);
}
}
bool isDiffMoreThanTwo(Tree* root)
{
return ((maxDepth(root) - minDepth(root)) >=2 );
}