Exercise II
- Differentiate binary trees, binary search trees, and balanced binary search trees based on the structure (balance) and ordering properties.
Exercise Could this tree be a BBST? If not, list every instance of all BBST violations by indicating roots of all non-BBST compliant subtrees.
Solution
A violation of the order property can be seen through an in-order traversal:
A, C, B, D, E, F, G, M, I, J, M, L, N, K, O, P
A violation of the balance property exists in nodes D, A, and G:
