Implement balanced factor with only 1 extra bit per node

Question

In the book Introduction To Algorithms - A Creative Approach, Question 4.18:

The AVL algorithms that were presented in Section 4.3.4 require balanced factors with three possible values: 1, 0, or -1. To represent three values we need 2 bits. Suggest a method for implementing these algorithms (with only a slight modification) with only 1 extra bit per node.

I have implemented AVL tree by recording each node's height instead of a balanced factor.

But I have no idea how to represent three values (1, 0, -1) with only 1 bit. I guess there must be some other information that can be employed to represent 1,0,-1, together with the 1 bit.

Could anyone help on this question?

Answer 1

If node don't have got two sons -you can calculate it else you can remember it in sons: one bit in left son and one in right son.