Review Questions

[answers are provided at the end]

Question 1. What is the maximum height of a binary tree with N nodes?

Question 2. What is the minimum height of a binary tree?

Question 3.  Consider a tree in which each node contains a maximum of 4 children (a quad tree). What is the minimum height of a quad tree that contains 21 nodes, what is the maximum height of a quad tree that contains 21 nodes?

Question 4. What is the maximum number of external nodes (or leaves) for a binary tree with height H?

Question 5. What is the maximum number of internal nodes (or leaves) for a binary tree with height H?

Question 6. Discuss advantages of using hash tables versus binary search trees

Question 7. Assuming each node in a BST takes 20 bytes of storage, how much memory is necessary to store a “perfect” binary tree of height 3? What is the amount of memory necessary if the tree is a “Full” tree of height 3 with minimal number of nodes?

Question 8. Draw the binary tree which would be created by inserting the following numbers in the order given. We insert them as follows. Start from root, if number is less go left, else go right. When you get to a leaf, insert the new node.

  50   30   25   75   82   28   63   70   4   43   74   35
 
Question 9: Implement a non-recursive method of finding the minimum node in the binary search tree. The method should return a node. 

Question 10: Computing the balance factor of a node (in an AVL tree) is expensive. What is the best way to handle this situation?

Question 1. What is the maximum height of a binary tree with N nodes?

Answer: N-1

Question 2. What is the minimum height of a binary tree with n nodes?

Answer: floor(log₂n)

Question 3.  Consider a tree in which each node contains a maximum of 4 children (a quad tree). What is the minimum height of a quad tree that contains 21 nodes, what is the maximum height of a quad tree that contains 21 nodes?

Answer: The max number of nodes in level k is 4^k. Therefore we will have 1 + 4 + 16 + 64 + … total nodes in a tree. So the min height is 2 and max height is 20

Question 4. What is the maximum number of external nodes (or leaves) for a binary tree with height H?

Answer: 2^H

Question 5. What is the maximum number of internal nodes (or leaves) for a binary tree with height H?

Answer: 2^H - 1

Question 6. Discuss advantages of using hash tables versus binary search trees

Answer: hash tables are great for applications that require quick search and updates, but do not require any order information. A “balanced” BST can maintains fairly quick search capability (log n) and order information

Question 7. Assuming each node in a BST takes 20 bytes of storage, how much memory is necessary to store a “perfect” binary tree of height 3? What is the amount of memory necessary if the tree is a “Full” tree of height 3 with minimal number of nodes?

Answer: A perfect binary tree of height 3 has 2³⁺¹ – 1 = 15 nodes. Therefore it requires 300 bytes to store the tree. If the tree is full of height 3 and minimum number of nodes, the tree will have 7 nodes. So we need 140 bytes to store the tree.

Question 8.

Question 9.

Question 10. Maintain the balance information in each node. The cost is only space to retain this number, but helps a lot in improving the computing time in balancing the tree.