Exercise I

  • Differentiate binary trees, binary search trees, and balanced binary search trees based on the structure (balance) and ordering properties.

Consider the following tree:

             20
            /  \
          10    30
               /  \
              5   40

Exercise Is this a binary tree, BST, or BBST? Why?

Solution

This tree is a binary tree. The 55 violates the BST property because it is smaller than 2020 (root), yet it is on the right subtree. All values in the right subtree should be greater than the current node (root in this case).

If it were a BST, it would have been a BBST because, for any node, its balance factor is 11, 00, or −1-1.

Exercise Using the following numbers {4,1,3,9,29,30,27,21}\{4, 1, 3, 9, 29, 30, 27, 21\}, construct a binary tree (that is not a BST or BBST), a BST (that is not a BBST), and a BBST.

Solution

Answers may vary.

Binary tree example: should only satisfy the property that each node has at most two children.

         1 
        / \
       3   29
      / \
     4  21
    / \
   30  9
      /
     27

BST example: should satisfy the binary tree property and the BST property.

         21
      /      \
     1       27
      \        \
       3       29
        \       \
         4       30
          \
           9

BBST example: needs to satisfy the binary tree property, BST property, and BBST height property.

        9
     /     \
   3        27
 /   \     /   \
1     4   21   29
                 \
                  30