126

I am just wondering if someone might be able to clarify the definition of a balanced tree for me. I have that "a tree is balanced if each sub-tree is balanced and the height of the two sub-trees differ by at most one.

I apologize if this is a dumb question, but does this definition apply to every node all the way down to the leaves of a tree or only to the left and right sub-trees immediately off the root? I guess another way to frame this would be, is it possible for internal nodes of a tree to be unbalanced and the whole tree to remain balanced?

1
  • 7
    Just wanted to add that we are talking about Comp. Science definition of a subtree: A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. For a regular mathematical definition (a subgraph of a tree which is itself a tree) it is not true. Nov 30, 2013 at 3:50

7 Answers 7

150

The constraint is generally applied recursively to every subtree. That is, the tree is only balanced if:

  1. The left and right subtrees' heights differ by at most one, AND
  2. The left subtree is balanced, AND
  3. The right subtree is balanced

According to this, the next tree is balanced:

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G  

The next one is not balanced because the subtrees of C differ by 2 in their height:

     A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G  

That said, the specific constraint of the first point depends on the type of tree. The one listed above is the typical for AVL trees.

Red-black trees, for instance, impose a softer constraint.

1
  • This looks to be the best answer here, with the exception that it should mention that, a balanced tree can be non binary. Aug 3, 2021 at 18:04
68

There are several ways to define "Balanced". The main goal is to keep the depths of all nodes to be O(log(n)).

It appears to me that the balance condition you were talking about is for AVL tree.
Here is the formal definition of AVL tree's balance condition:

For any node in AVL, the height of its left subtree differs by at most 1 from the height of its right subtree.

Next question, what is "height"?

The "height" of a node in a binary tree is the length of the longest path from that node to a leaf.

There is one weird but common case:

People define the height of an empty tree to be (-1).

For example, root's left child is null:

              A  (Height = 2)
           /     \
(height =-1)       B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1
                    \
                     C (Height = 0)

Two more examples to determine:

Yes, A Balanced Tree Example:

        A (h=3)
     /     \
 B(h=1)     C (h=2)        
/          /   \
D (h=0)  E(h=0)  F (h=1)
               /
              G (h=0)

No, Not A Balanced Tree Example:

        A (h=3)
     /     \
 B(h=0)     C (h=2)        <-- Unbalanced: 2-0 =2 > 1
           /   \
        E(h=1)  F (h=0)
        /     \
      H (h=0)   G (h=0)      
3
  • 1
    Note that this definition allows unbalanced subtrees of balanced trees. (eg. extend the balanced tree example above by adding a child to D and another one to G) Is this intended?
    – gen
    Dec 4, 2016 at 13:56
  • 3
    No it doesn't. "For any node in AVL, the height of its left subtree differs by at most 1 from the height of its right subtree." If you add a child to D, then B won't follow the above rule. Hence, the tree wont be a BBT.
    – John Red
    Apr 15, 2018 at 12:34
  • 2
    your answer is very verbose and not accurate Feb 4, 2019 at 13:02
10

There's no difference between these two things. Think about it.

Let's take a simpler definition, "A positive number is even if it is zero or that number minus two is even." Does this say 8 is even if 6 is even? Or does this say 8 is even if 6, 4, 2, and 0 are even?

There's no difference. If it says 8 is even if 6 is even, it also says 6 is even if 4 is even. And thus it also says 4 is even if 2 is even. And thus it says 2 is even if 0 is even. So if it says 8 is even if 6 is even, it (indirectly) says 8 is even if 6, 4, 2, and 0 are even.

It's the same thing here. Any indirect sub-tree can be found by a chain of direct sub-trees. So even if it only applies directly to direct sub-trees, it still applies indirectly to all sub-trees (and thus all nodes).

7
  • 1
    Let's say the value of the root is 15. Down the right, I have 16,17,18. Down the left I have 14,13,12. Is that a balanced tree? The height of each sub-tree off the node is within one. But take the first node below the root to the right, it has no left children but the height of its right children is 2. So that node is not balanced. Is that correct?
    – Mark Soric
    Nov 4, 2011 at 21:01
  • 1
    Correct. Thus the tree is not balanced. Nov 4, 2011 at 21:02
  • 1
    So in order for a tree to be balanced - every node has to be balanced. Beauty - Thanks very much for your help.
    – Mark Soric
    Nov 4, 2011 at 21:03
  • 1
    @DavidSchwartz why are we trying to use a balanced tree? why do we care if a tree is balanced or not?
    – Dejell
    Jun 23, 2013 at 18:44
  • 3
    This is, by-far, the most complex answer I've seen on SO - to any question. Sorry to say this.
    – Trevor
    Dec 3, 2013 at 20:37
4

Balanced tree is a tree whose height is of order of log(number of elements in the tree).

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

The definition given "a tree is balanced of each sub-tree is balanced and the height of the two sub-trees differ by at most one" is followed by AVL trees.

Since, AVL trees are balanced but not all balanced trees are AVL trees, balanced trees don't hold this definition and internal nodes can be unbalanced in them. However, AVL trees require all internal nodes to be balanced.

3

the aim of balanced tree is to reach the leaf in a minimum of traversal (min height). The degree of the tree is the number of branches minus 1. A Balanced tree may be not Binary.

1
  1. The height of a node in a tree is the length of the longest path from that node downward to a leaf, counting both the start and end vertices of the path.
  2. A node in a tree is height-balanced if the heights of its subtrees differ by no more than 1.
  3. A tree is height-balanced if all of its nodes are height-balanced.
6
  • Can be said simpler. A tree where no leaf is much farther away from the root than any other leaf.
    – parsecer
    Dec 14, 2020 at 13:08
  • Statements like "much farther away" is ambiguous. A precise definition is needed for implementation in code.
    – John Paul
    Dec 15, 2020 at 17:29
  • Bruh. As close to the root as the closest leaf node or only one node farther then. Still much simpler
    – parsecer
    Dec 16, 2020 at 4:15
  • The one given above is the official definition. It can be implemented easily using recursion.
    – John Paul
    Dec 17, 2020 at 5:05
  • @parsecer where's the simplicity in : no leaf is much farther away from ? I had to read it more than 3 times, and still not so fluidly understandable. Aug 3, 2021 at 17:57
0

The recursive definition of looking at the left sub-tree and right sub-tree could be made equivalent to the following definition:

A binary tree is balancing if and only if, for every node N, the Height of its left sub-tree and the Height of its right sub-tree differ at most by 1.

Notice that this should hold for all nodes. They are equivalent definitions. The latter maybe more understandable. You could also think of it as an "iterative definition", compared to the "recursive definition"

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.