Mark the balance factor of each node on the tree given in the below figure and state whether it is height-balanced.

The...

Question

Mark the balance factor of each node on the tree given in the below figure and state whether it is height-balanced.

The tree is as follows:
         a
        / \
       b   c
      / \
     d   e
          \
           f

(Node 'a' is the root; 'b' and 'c' are children of 'a'; 'd' and 'e' are children of 'b'; 'f' is the right child of 'e')

Accepted Answer

Balance factors: d=0, f=0, c=0, e=-1, b=-1, a=2. The tree is NOT height-balanced because node 'a' has a balance factor of magnitude 2. An AVL tree is a binary search tree where, for every node, the difference in heights of its left and right subtrees is at most 1 (this difference is called the balance factor). We compute the balance factor for every node in the given tree and check if all are in the set {-1, 0, +1}. If any node has |balance factor| > 1, the tree is not height-balanced.

Mark the balance factor of each node on the tree given in the below figure and state whether it is height-balanced. The tree is as follows: a / \ b c / \ d e \ f (Node 'a' is the root; 'b' and 'c' are children of 'a'; 'd' and 'e' are children of 'b'; 'f' is the right child of 'e')