Announcing Stack Overflow Documentation



Sign up and start helping → Learn more about Documentation →

It's been a while from those school years. Got a job as IT specialist at a hospital. Trying to move to do some actual programming now. I'm working on binary trees now, and I was wondering what would be the best way to determine if the tree is height-balanced.

I was thinking of something along this:

public boolean isBalanced(Node root){
        return true;  //tree is empty
        int lh = root.left.height();
        int rh = root.right.height();
            return false;
    return true;

Is this a good implementation? or am I missing something?

share|improve this question

23 Answers 23

Stumbled across this old question while searching for something else. I notice that you never did get a complete answer.

The way to solve this problem is to start by writing a specification for the function you are trying to write.

Specification: A well-formed binary tree is said to be "height-balanced" if (1) it is empty, or (2) its left and right children are height-balanced and the height of the left tree is within 1 of the height of the right tree.

Now that you have the specification, the code is trivial to write. Just follow the specification:

    return (tree is empty) or 
           (IsHeightBalanced(tree.left) and
            IsHeightBalanced(tree.right) and
            abs(Height(tree.left) - Height(tree.right)) <= 1)

Translating that into the programming language of your choice should be trivial.

Bonus exercise: this naive code sketch traverses the tree far too many times when computing the heights. Can you make it more efficient?

Super bonus exercise: suppose the tree is massively unbalanced. Like, a million nodes deep on one side and three deep on the other. Is there a scenario in which this algorithm blows the stack? Can you fix the implementation so that it never blows the stack, even when given a massively unbalanced tree?

UPDATE: Donal Fellows points out in his answer that there are different definitions of 'balanced' that one could choose. For example, one could take a stricter definition of "height balanced", and require that the path length to the nearest empty child is within one of the path to the farthest empty child. My definition is less strict than that, and therefore admits more trees.

One can also be less strict than my definition; one could say that a balanced tree is one in which the maximum path length to an empty tree on each branch differs by no more than two, or three, or some other constant. Or that the maximum path length is some fraction of the minimum path length, like a half or a quarter.

It really doesn't matter usually. The point of any tree-balancing algorithm is to ensure that you do not wind up in the situation where you have a million nodes on one side and three on the other. Donal's definition is fine in theory, but in practice it is a pain coming up with a tree-balancing algorithm that meets that level of strictness. The performance savings usually does not justify the implementation cost. You spend a lot of time doing unnecessary tree rearrangements in order to attain a level of balance that in practice makes little difference. Who cares if sometimes it takes forty branches to get to the farthest leaf in a million-node imperfectly-balanced tree when it could in theory take only twenty in a perfectly balanced tree? The point is that it doesn't ever take a million. Getting from a worst case of a million down to a worst case of forty is usually good enough; you don't have to go all the way to the optimal case.

share|improve this answer
+1 for only correct answer, I can't believe no one was able to answer this for 8 months... – BlueRaja - Danny Pflughoeft Feb 1 '10 at 20:09
Answer to the "exercises" below… – Potatoswatter Feb 2 '10 at 2:56
Answered Bonus exercise below. – Brian Feb 2 '10 at 14:25
sdk's answer below seems to be right and only makes 2 tree traversals so is O(n). Unless I'm missing somethinig, does that not solve at least your first bonus question. You can of course also use dynamic programming and your solution to cache intermediate heights – Aly May 10 '11 at 13:01
Theoretically, I would have to side with Donal Fellows' definition still. – Dhruv Gairola May 6 '12 at 16:30

Balance is a truly subtle property; you think you know what it is, but it's so easy to get wrong. In particular, even Eric Lippert's (good) answer is off. That's because the notion of height is not enough. You need to have the concept of minimum and maximum heights of a tree (where the minimum height is the least number of steps from the root to a leaf, and the maximum is... well, you get the picture). Given that, we can define balance to be:

A tree where the maximum height of any branch is no more than one more than the minimum height of any branch.

(This actually implies that the branches are themselves balanced; you can pick the same branch for both maximum and minimum.)

All you need to do to verify this property is a simple tree traversal keeping track of the current depth. The first time you backtrack, that gives you a baseline depth. Each time after that when you backtrack, you compare the new depth against the baseline

  • if it's equal to the baseline, then you just continue
  • if it is more than one different, the tree isn't balanced
  • if it is one off, then you now know the range for balance, and all subsequent depths (when you're about to backtrack) must be either the first or the second value.

In code:

class Tree {
    Tree left, right;
    static interface Observer {
        public void before();
        public void after();
        public boolean end();
    static boolean traverse(Tree t, Observer o) {
        if (t == null) {
            return o.end();
        } else {
            try {
                if (traverse(left, o))
                    return traverse(right, o);
                return false;
            } finally {
    boolean balanced() {
        final Integer[] heights = new Integer[2];
        return traverse(this, new Observer() {
            int h;
            public void before() { h++; }
            public void after() { h--; }
            public boolean end() {
                if (heights[0] == null) {
                    heights[0] = h;
                } else if (Math.abs(heights[0] - h) > 1) {
                    return false;
                } else if (heights[0] != h) {
                    if (heights[1] == null) {
                        heights[1] = h;
                    } else if (heights[1] != h) {
                        return false;
                return true;

I suppose you could do this without using the Observer pattern, but I find it easier to reason this way.

[EDIT]: Why you can't just take the height of each side. Consider this tree:

       /  \
      /    \
     /      \_____
    /\      /     \_
   /  \    /      / \
  /\   C  /\     /   \
 /  \    /  \   /\   /\
A    B  D    E F  G H  J

OK, a bit messy, but each side of the root is balanced: C is depth 2, A, B, D, E are depth 3, and F, G, H, J are depth 4. The height of the left branch is 2 (remember the height decreases as you traverse the branch), the height of the right branch is 3. Yet the overall tree is not balanced as there is a difference in height of 2 between C and F. You need a minimax specification (though the actual algorithm can be less complex as there should be only two permitted heights).

share|improve this answer
Ah, good point. You could have a tree which is h(LL)=4, h(LR)=3, h(RL)=3, h(RR)=2. Thus, h(L)=4 and h(R)=3, so it would appear balanced to the earlier algorithm, but with a max/min depth of 4/2, this is not balanced. This would probably make more sense with a picture. – Tim Apr 7 '10 at 22:04
That's what I've just added (with the world's nastiest ASCII graphic tree). – Donal Fellows Apr 7 '10 at 22:10
@DonalFellows: you mentioned the height of the left branch is 2. but the left branch has 4 nodes including the root and leaf A. The height will be 3 in this case correct – brain storm Oct 28 '13 at 19:16

This only determines if the top level of the tree is balanced. That is, you could have a tree with two long branches off the far left and far right, with nothing in the middle, and this would return true. You need to recursively check the root.left and root.right to see if they are internally balanced as well before returning true.

share|improve this answer
However, if the code had a max and min height method, if it's globally balanced it would be locally balanced as well. – Ari Mar 13 '15 at 4:27

Bonus exercise response. The simple solution. Obviously in a real implementation one might wrap this or something to avoid requiring the user to include height in their response.

IsHeightBalanced(tree, out height)
    if (tree is empty)
        height = 0
        return true
    balance = IsHeightBalanced(tree.left, heightleft) and IsHeightBalanced(tree.right, heightright)
    height = max(heightleft, heightright)+1
    return balance and abs(heightleft - heightright) <= 1     
share|improve this answer
Nicely done! ------- – Eric Lippert Feb 2 '10 at 14:50
If the tree is bigger than a few hundred layers high, you get a stackoverflow exception. You've done it efficiently, but it does not handle medium or large size data sets. – Eric Leschinski May 3 '15 at 20:35

The definition of a height-balanced binary tree is:

Binary tree in which the height of the two subtrees of every node never differ by more than 1.

So, An empty binary tree is always height-balanced.
A non-empty binary tree is height-balanced if:

  1. Its left subtree is height-balanced.
  2. Its right subtree is height-balanced.
  3. The difference between heights of left & right subtree is not greater than 1.

Consider the tree:

     / \
    C   D

As seen the left subtree of A is height-balanced (as it is empty) and so is its right subtree. But still the tree is not height-balanced as condition 3 is not met as height of left-subtree is 0 and height of right sub-tree is 2.

Also the following tree is not height balanced even though the height of left and right sub-tree are equal. Your existing code will return true for it.

     /  \ 
    B    C
   /      \
  D        G
 /          \
E            H

So the word every in the def is very important.

This will work:

int height(treeNodePtr root) {
        return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));

bool isHeightBalanced(treeNodePtr root) {
        return (root == NULL) ||
                (isHeightBalanced(root->left) &&
                isHeightBalanced(root->right) &&
                abs(height(root->left) - height(root->right)) <=1);

Ideone Link

share|improve this answer
So this answer helped me a lot. However, I found the free [MIT intro to algorithms course] seems to contradict condition 3. Page 4 shows a RB tree where the height of the left branch is 2 and the right branch is 4. Can you offer some clarification to me? Perhaps I don't get the definition of a subtree. [1]:ocw.mit.edu/courses/electrical-engineering-and-computer-science/… – i8abug Aug 30 '11 at 17:45
The difference seems to come from this definition in the course notes. All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x) – i8abug Aug 30 '11 at 17:54
Just to follow up, I found a definition that changes point (3) in your answer to "every leaf is 'not more than a certain distance' away from the root than any other leaf". This seems to satisfy both cases. Here is the link from some random course ware – i8abug Aug 31 '11 at 3:26

Post order solution, traverse the tree only once. Time complexity is O(n), space is O(1), it's better than top-down solution. I give you a java version implementation.

public static <T> boolean isBalanced(TreeNode<T> root){
    return checkBalance(root) != -1;

private static <T> int checkBalance(TreeNode<T> node){
    if(node == null) return 0;
    int left = checkBalance(node.getLeft());

    if(left == -1) return -1;

    int right = checkBalance(node.getRight());

    if(right == -1) return -1;

    if(Math.abs(left - right) > 1){
        return -1;
        return 1 + Math.max(left, right);
share|improve this answer
nice solution, but space complexity should be O(H) where H is the height of the tree. This is because stack allocation for recursion. – legrass Aug 15 '15 at 10:43
What does left == -1 mean? When would that ever be the case? Do we assume the recursive call implies that left == -1 is true if all the subtrees of the left children are unbalanced? – Aspen Jan 13 at 18:49
left == 1 means left subtree is unbalanced, then the whole tree is unbalanced. We do not have to check right subtree anymore, and can return -1. – tning Feb 22 at 2:15
Time complexity is O(n) because you have to go through all the elements. And, if you had x nodes and it will take y time to check balance; if you had 2x nodes, it will take 2y time to check balance. That all sound right? – Jack May 15 at 5:24

What balanced means depends a bit on the structure at hand. For instance, A B-Tree cannot have nodes more than a certain depth from the root, or less for that matter, all data lives at a fixed depth from the root, but it can be out of balance if the distribution of leaves to leaves-but-one nodes is uneven. Skip-lists Have no notion at all of balance, relying instead on probability to achieve decent performance. Fibonacci trees purposefully fall out of balance, postponing the rebalance to achieve superior asymptotic performance in exchange for occasionally longer updates. AVL and Red-Black trees attach metadata to each node to attain a depth-balance invariant.

All of these structures and more are present in the standard libraries of most common programming systems (except python, RAGE!). Implementing one or two is good programming practice, but its probably not a good use of time to roll your own for production, unless your problem has some peculiar performance need not satisfied by any off-the-shelf collections.

share|improve this answer

This is being made way more complicated than it actually is.

The algorithm is as follows:

  1. Let A = depth of the highest-level node
  2. Let B = depth of the lowest-level node

  3. If abs(A-B) <= 1, then the tree is balanced

share|improve this answer
Simple and straight! – Wasim Thabraze Dec 3 '14 at 5:51
Two problems, it's not as efficient as it could be, you are making two passes over the entire tree. And for trees that have one node to the left, and thousands to the right, you unnecessarily step through the entire thing, when you could have stopped after 3 checks. – Eric Leschinski May 3 '15 at 20:38

Balancing usually depends on the length of the longest path on each direction. The above algorithm is not going to do that for you.

What are you trying to implement? There are self-balancing trees around (AVL/Red-black). In fact, Java trees are balanced.

share|improve this answer

If this is for your job, I suggest:

  1. do not reinvent the wheel and
  2. use/buy COTS instead of fiddling with bits.
  3. Save your time/energy for solving business problems.
share|improve this answer
public boolean isBalanced(TreeNode root)
    return (maxDepth(root) - minDepth(root) <= 1);

public int maxDepth(TreeNode root)
    if (root == null) return 0;

    return 1 + max(maxDepth(root.left), maxDepth(root.right));

public int minDepth (TreeNode root)
    if (root == null) return 0;

    return 1 + min(minDepth(root.left), minDepth(root.right));
share|improve this answer
I think this solution is not correct.If you pass a tree that has a single node i.e. a root it will return as maxDepth 1 (same for minDepth). The correct depth though should be 0.A tree's root has always 0 depth – Cratylus Dec 11 '11 at 14:26
#include <iostream>
#include <deque>
#include <queue>

struct node
    int data;
    node *left;
    node *right;

bool isBalanced(node *root)
    if ( !root)
        return true;

    std::queue<node *> q1;
    std::queue<int>  q2;
    int level = 0, last_level = -1, node_count = 0;


    while ( !q1.empty() )
        node *current = q1.front();
        level = q2.front();


        if ( level )

                if ( current->left )
                        q2.push(level + 1);

                if ( current->right )
                        q2.push(level + 1);

        if ( level != last_level )
            std::cout << "Check: " << (node_count ? node_count - 1 : 1) << ", Level: " << level << ", Old level: " << last_level << std::endl;
            if ( level && (node_count - 1) != (1 << (level-1)) )
                return false;

            last_level = q2.front();
            if ( level ) node_count = 1;

    return true;

int main()
    node tree[15];

    tree[0].left  = &tree[1];
    tree[0].right = &tree[2];
    tree[1].left  = &tree[3];
    tree[1].right = &tree[4];
    tree[2].left  = &tree[5];
    tree[2].right = &tree[6];
    tree[3].left  = &tree[7];
    tree[3].right = &tree[8];
    tree[4].left  = &tree[9];   // NULL;
    tree[4].right = &tree[10];  // NULL;
    tree[5].left  = &tree[11];  // NULL;
    tree[5].right = &tree[12];  // NULL;
    tree[6].left  = &tree[13];
    tree[6].right = &tree[14];
    tree[7].left  = &tree[11];
    tree[7].right = &tree[12];
    tree[8].left  = NULL;
    tree[8].right = &tree[10];
    tree[9].left  = NULL;
    tree[9].right = &tree[10];
    tree[10].left = NULL;
    tree[10].right= NULL;
    tree[11].left = NULL;
    tree[11].right= NULL;
    tree[12].left = NULL;
    tree[12].right= NULL;
    tree[13].left = NULL;
    tree[13].right= NULL;
    tree[14].left = NULL;
    tree[14].right= NULL;

    std::cout << "Result: " << isBalanced(tree) << std::endl;

    return 0;
share|improve this answer
you might want to add some comments – jgauffin Dec 6 '11 at 19:06

Note 1: The height of any sub-tree is computed only once.

Note 2: If the left sub-tree is unbalanced then the computation of the right sub-tree, potentially containing million elements, is skipped.

// return height of tree rooted at "tn" if, and only if, it is a balanced subtree
// else return -1
int maxHeight( TreeNode const * tn ) {
    if( tn ) {
        int const lh = maxHeight( tn->left );
        if( lh == -1 ) return -1;
        int const rh = maxHeight( tn->right );
        if( rh == -1 ) return -1;
        if( abs( lh - rh ) > 1 ) return -1;
        return 1 + max( lh, rh );
    return 0;

bool isBalanced( TreeNode const * root ) {
    // Unless the maxHeight is -1, the subtree under "root" is balanced
    return maxHeight( root ) != -1;
share|improve this answer

Well, you need a way to determine the heights of left and right, and if left and right are balanced.

And I'd just return height(node->left) == height(node->right);

As to writing a height function, read: http://stackoverflow.com/questions/717725/understanding-recursion/717839#717839

share|improve this answer
You want left and right heights to be within 1, not necessarily equal. – Alex B Apr 13 '09 at 3:36

What kind of tree are you talking about? There are self-balancing trees out there. Check their algorithms where they determine if they need to reorder the tree in order to maintain balance.

share|improve this answer

Here is a version based on a generic depth-first traversal. Should be faster than the other correct answer and handle all the mentioned "challenges." Apologies for the style, I don't really know Java.

You can still make it much faster by returning early if max and min are both set and have a difference >1.

public boolean isBalanced( Node root ) {
    int curDepth = 0, maxLeaf = 0, minLeaf = INT_MAX;
    if ( root == null ) return true;
    while ( root != null ) {
        if ( root.left == null || root.right == null ) {
            maxLeaf = max( maxLeaf, curDepth );
            minLeaf = min( minLeaf, curDepth );
        if ( root.left != null ) {
            curDepth += 1;
            root = root.left;
        } else {
            Node last = root;
            while ( root != null
             && ( root.right == null || root.right == last ) ) {
                curDepth -= 1;
                last = root;
                root = root.parent;
            if ( root != null ) {
                curDepth += 1;
                root = root.right;
    return ( maxLeaf - minLeaf <= 1 );
share|improve this answer
A nice attempt but it clearly does not work. Let x be a null node. Let a non-null tree node be denoted as (LEFT VALUE RIGHT). Consider the tree (x A (x B x)). "root" points to nodes A, B, A, B, A, B ... forever. Care to try again? A hint: it's actually easier without parent pointers. – Eric Lippert Feb 2 '10 at 3:18
@Eric: Oops, fixed (I think). Well, I'm trying to do this without O(depth) memory, and if the structure doesn't have parent pointers (it often does), you need to use a stack. – Potatoswatter Feb 2 '10 at 4:50
So what you're telling me is you'd rather use O(n) permanent memory in parent pointers to avoid allocating O(d) temporary memory, where log n <= d <= n ? This seems like a false economy. – Eric Lippert Feb 2 '10 at 6:20
Unfortunately, though you've fixed the problem with the traversal, there's a far bigger problem here. This does not test whether a tree is balanced, it tests whether a tree has all its leaves close to the same level. That's not the definition of "balanced" that I gave. Consider the tree ((((x D x) C x) B x) A x). Your code reports that this is "balanced" when it obviously is maximally unbalanced. Care to try again? – Eric Lippert Feb 2 '10 at 6:37
@Eric reply 1: not a false economy if you already use the parent pointers for something else. reply 2: sure, why not. This is a bizarre way of debugging… I shouldn't be blindly writing traversals of anything at 4 am… – Potatoswatter Feb 2 '10 at 10:48

If binary tree is balanced or not can be checked by Level order traversal:

private boolean isLeaf(TreeNode root) {
    if (root.left == null && root.right == null)
        return true;
    return false;

private boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;
    Vector<TreeNode> queue = new Vector<TreeNode>();
    int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
    while (!queue.isEmpty()) {
        int elementCount = queue.size();
        while (elementCount > 0) {
            TreeNode node = queue.remove(0);
            if (isLeaf(node)) {
                if (minLevel > level)
                    minLevel = level;
                if (maxLevel < level)
                    maxLevel = level;
            } else {
                if (node.left != null)
                if (node.right != null)
        if (abs(maxLevel - minLevel) > 1) {
            return false;

    return true;
share|improve this answer

Here's what i have tried for Eric's bonus exercise. I try to unwind of my recursive loops and return as soon as I find a subtree to be not balanced.

int heightBalanced(node *root){
    int i = 1;
    heightBalancedRecursive(root, &i);
    return i; 

int heightBalancedRecursive(node *root, int *i){

    int lb = 0, rb = 0;

    if(!root || ! *i)  // if node is null or a subtree is not height balanced
           return 0;  

    lb = heightBalancedRecursive(root -> left,i);

    if (!*i)         // subtree is not balanced. Skip traversing the tree anymore
        return 0;

    rb = heightBalancedRecursive(root -> right,i)

    if (abs(lb - rb) > 1)  // not balanced. Make i zero.
        *i = 0;

    return ( lb > rb ? lb +1 : rb + 1); // return the current height of the subtree
share|improve this answer
public int height(Node node){
    if(node==null)return 0;
        int l=height(node.leftChild);
        int r=height(node.rightChild);

public boolean balanced(Node n){

    int l= height(n.leftChild);
    int r= height(n.rightChild);

    System.out.println(l + " " +r);
        return false;
        return true;
share|improve this answer

An empty tree is height-balanced. A non-empty binary tree T is balanced if:

1) Left subtree of T is balanced

2) Right subtree of T is balanced

3) The difference between heights of left subtree and right subtree is not more than 1.

/* program to check if a tree is height-balanced or not */
#define bool int

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
  int data;
  struct node* left;
  struct node* right;

/* The function returns true if root is balanced else false
   The second parameter is to store the height of tree.  
   Initially, we need to pass a pointer to a location with value 
   as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
  /* lh --> Height of left subtree 
     rh --> Height of right subtree */   
  int lh = 0, rh = 0;  

  /* l will be true if left subtree is balanced 
    and r will be true if right subtree is balanced */
  int l = 0, r = 0;

  if(root == NULL)
    *height = 0;
     return 1;

  /* Get the heights of left and right subtrees in lh and rh 
    And store the returned values in l and r */   
  l = isBalanced(root->left, &lh);
  r = isBalanced(root->right,&rh);

  /* Height of current node is max of heights of left and 
     right subtrees plus 1*/   
  *height = (lh > rh? lh: rh) + 1;

  /* If difference between heights of left and right 
     subtrees is more than 2 then this node is not balanced
     so return 0 */
  if((lh - rh >= 2) || (rh - lh >= 2))
    return 0;

  /* If this node is balanced and left and right subtrees 
    are balanced then return true */
  else return l&&r;


/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
    struct node* node = (struct node*)
                                malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;


int main()
  int height = 0;

  /* Constructed binary tree is
           /   \
         2      3
       /  \    /
     4     5  6
  struct node *root = newNode(1);  
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);
  root->left->left->left = newNode(7);

  if(isBalanced(root, &height))
    printf("Tree is balanced");
    printf("Tree is not balanced");    

  return 0;

Time Complexity: O(n)

share|improve this answer

To have a better performance specially on huge trees you can save the height in each node so it is a trade off space Vs performance:

class Node {
    Node left;
    Node right;
    int value;
    int height;

Example of implementing the addition and same for deletion

void addNode(Node root,int v)
{    int height =0;
     while(root != null)
         // Since we are adding new node so the height 
         // will increase by one in each node we will pass by
         root.height += 1;
         else if(v > root.value){
            root = root.left();
         root = root.right();


         Node n = new Node(v , height);
         root = n;         
int treeMaxHeight(Node root)
 return Math.Max(root.left.height,root.right.height);

int treeMinHeight(Node root)
 return Math.Min(root.left.height,root.right.height);


Boolean isNodeBlanced(Node root)
   if (treeMaxHeight(root) - treeMinHeight(root) > 2)
       return false;

  return true;

Boolean isTreeBlanced (Node root)
    if(root == null || isTreeBalanced(root.left) && isTreeBalanced(root.right) && isNodeBlanced(root))
    return true;

  return false;

share|improve this answer
    static boolean isBalanced(Node root) {
    //check in the depth of left and right subtree
    int diff = depth(root.getLeft()) - depth(root.getRight());
    if (diff < 0) {
        diff = diff * -1;
    if (diff > 1) {
        return false;
    //go to child nodes
    else {
        if (root.getLeft() == null && root.getRight() == null) {
            return true;
        } else if (root.getLeft() == null) {
            if (depth(root.getRight()) > 1) {
                return false;
            } else {
                return true;
        } else if (root.getRight() == null) {
            if (depth(root.getLeft()) > 1) {
                return false;
            } else {
                return true;
        } else if (root.getLeft() != null && root.getRight() != null && isBalanced(root.getLeft()) && isBalanced(root.getRight())) {
            return true;
        } else {
            return false;
share|improve this answer

Wouldn't this work?

return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );

Any unbalanced tree would always fail this.

share|improve this answer
Many balanced trees will fail it, too. – Brian Feb 2 '10 at 20:45

Your Answer


