LexisNexis Interview Question
not exactly...
even if the depth differ by one, they may be unbalanced...
Consider the following tree
------A------
----B---C----
--D--E-F-----
G------------
This tree is not balanced however the difference between the leaf nodes is 1. Hence we need to find some other logic.
r u sure?
I think we have to use both first and second solutions i.e the difference between the depths should not be more than 2 and 2^depth >total nodes>2^(depth-1)
then only it will be balanced.
I think the above tree is not balanced
i think the above tree is balanced ...
trees with a worst-case height of log(n) are called balanced trees...and it is also written in the questions" the level diff should not greater than one at each node .i think this is the only def of balanced tree..hey name mate :) , plz correct me if i am wrong.. thanks
I think that checking the difference between left and right subtree at every node might not work - I can't quite come up with a counter-example though.
What probably needs to be done is to find the max height of the tree and then the min height and then check that the difference is <= 1. Max height == the height of the leaf node that's furthest away from the root; min height == height of the leaf node that's closest to the root.
when you go from bottom to top(by recursion) you do not need to check max or min hight at every node just check whether the height difference is |1| or not...i think first solution is enough...
a counter example is:
A
/ \
/ \
/ \
B C
/ \ / \
D E F G
/ \ \ \
H I J K
\
L
In this case, above mentioned algo gives a balanced tree. This is a balanced tree by normal definition but this isn't one according to the given question.
MaxDepth - MinDepth should be < 1 for tree to be balanced.
Both can easily be found using a recursive method.
// return Max(node.left + 1, node.right + 1);
How about the next solution?
public static int getMaxDepth(Node root)
{
if(root==null) return 0;
return 1+Max(getMaxDepth(root.left),getMaxDepth(root.right));
}
public static int getMinDepth(Node root)
{
if(root==null) return 0;
return 1+Min(getMinDepth(root.left),getMinDepth(root.right));
}
public static boolean isBalanced(Node root)
{
if(getMaxDepth(root)-getMinDepth(root)<=1)
{
return true;
}
return false;
}
-----------------A-----------------
---------B--------------C---------
---- D-----E-------F-----G-----
---H--I------J-------K-------M--
--L--------------------------------
If we have this tree, then it is balanced. But, MinDepth of A will be calculated as 3 whereas MaxDepth as 5. So it will give it as an unbalanced tree.
Please correct me if I am taking this incorrectly.
I think this should work.
struct TN{
int data;
struct TN* left;
struct TN* right;
};
///////////////////////////////////////////////////////////////
//returns length of longest path from root to a leaf
int getHeight(TN *root)
{
if(root == NULL)
return 0;
return(1 + max(getHeight(root->left), getHeight(root->right)));
}
/////////////////////////////////////////////////////////////
//returns length of minimum path from root to a leaf
int getMinHeight(TN *root)
{
if(root == NULL)
return 0;
int lMinHeight = getMinHeight(root->left);
int rMinHeight = getMinHeight(root->right);
if(lMinHeight == 0 || rMinHeight == 0)
{return 1+max(lMinHeight,rMinHeight);
}
else
{return 1 + min(lMinHeight, rMinHeight);}
}
////////////////////////////////////////////////////////
//function to check balance of tree
bool checkBalance(TN *root)
{
int maxHeight = getHeight(root);
int minHeight = getMinHeight(root);
if(maxHeight - minHeight > 1)
return false;
else
return true;
}
bool IsBalancedOrNot(Node *root, int &height)
{
if (root == NULL) {
height = 0;
return true;
}
int lHeight = 0, rHeight = 0;
if (IsBalancedOrNot(root->left, &lHeight) && IsBalancedOrNot(root->right, &rHeight)
{
height = max(lHeight, rheight) + 1;
return ( abs(lHeight-rHeight) <=1 );
}
else
return false;
}
Find the depth of the tree recursively. On the way back compare the depth of left tree and right tree if they differ by more than one then you have an unbalanced tree.
- Anonymous November 17, 2010