8.7 Review questions

This final section contains some review questions about the contents of this chapter.

8.7.1 Review questions: Binary tree definition

Which statement is false?

  • Look carefully at the definition for a binary tree.
  • It states that every binary tree is either empty, or it has a root node and two binary trees as children.
  • So, every binary tree node has two children, but not every binary tree has a node.

What is the minimum number of nodes in a complete binary tree with height 3?

  • Start filling in the tree level by level.
  • Stop when you draw the first node at level 3.

Select the one true statement.

  • Not every binary tree is either complete or full.
  • Not every complete binary tree is full.
  • Not every full binary tree is complete.
  • Some complete trees are full.

What is the minimum number of nodes in a full binary tree with height 3?

  • First, draw a vertical chain of 4 nodes. This is a tree with height 3.
  • Next, add nodes to make the tree be full.

Suppose T is a binary tree with 14 nodes. What is the minimum possible height of T?

  • Try drawing this as a complete treee.
  • That is, build a tree of 14 nodes by filling it in level by level.

What is the minimum number of internal nodes in a binary tree with 8 nodes?

  • Try drawing some trees. Your best bet is to try and make it full.

8.7.2 Review questions: Example binary tree

Here’s an example binary tree

How many internal nodes does this tree have?

  • Anything that is not a leaf node is an internal node. Internal nodes might have 1 or 2 children.

What is the height of this tree?

  • Count the number of steps to the deepest node.

How many leaf nodes does this tree have?

  • Anything that has no children is a leaf node.

How many nodes in the tree have at least one sibling?

  • Siblings must have the same parent. If a node has two children, then each such child has a sibling.

How many descendents does the root of this tree have?

  • Every node except the root is a descendent.

What is the depth of this tree?

  • Nodes have depth.

Which statement is correct?

  • Do any internal nodes have only one child? If so, the tree is not full.
  • A complete tree fills in nodes level by level, with the bottom level filled in from left to right.

8.7.3 Review questions: Binary tree traversals

Visiting each element in a tree is known as:

Answer TRUE or FALSE.

If you are given the order of the nodes as visited by a postorder traversal and the order of the nodes as visited by an inorder traversal, do you have enough information to reconstruct the original tree? Assume that the nodes all have unique values.

  • Build yourself a small example tree of about 6 or 7 nodes and see what happens.
  • Consider the example where the root has value A. In the postorder traversal, the left subtree is printed, then the right subtree, then A. In the inorder traversal, the left subtree comes first, then the A, then the right subtree.
  • From this information, we always know the root, the contents of its left subtree, and the contents of its right subtree.
  • We can apply this concept recursively to reconstruct the left subtree and the right subtree.

Answer TRUE or FALSE.

If you are given the order of the nodes as visited by a preorder traversal and the order of the nodes as visited by an inorder traversal, do you have enough information to reconstruct the original tree? Assume that the nodes all have unique values.

  • Build yourself a small example tree of about 6 or 7 nodes and see what happens.
  • Consider the example where the root has value A. In the preorder traversal, that A is printed first. In the inorder traversal, the left subtree comes first, then the A, then the right subtree.
  • From this information, we always know the root, the contents of its left subtree, and the contents of its right subtree.
  • We can apply this concept recursively to reconstruct the left subtree and the right subtree.

Answer TRUE or FALSE.

If you are given the order of the nodes as visited by a preorder traversal and the order of the nodes as visited by a postorder traversal, do you have enough information to reconstruct the original tree? Assume that the nodes all have unique values.

  • Consider this example: The preorder traversal prints ABC, and the postorder traversal prints CBA. Can you determine the original tree from this information?
  • In general, if a node has only one subtree, then the preorder and postorder traversals do not give you enough information to determine which side the subtree goes on.

Answer TRUE or FALSE.

When you print out the nodes of binary tree, the leaf nodes appear in the same relative order for the preorder, inorder, and postorder traversals.

  • Take a small binary tree with three or four leaf nodes and see what happens with the traversals.
  • Since all 3 traversals print the left subtree before the right subtree, the leaves have to get printed in the same order.

The nn nodes in a binary tree can be visited in:

  • This would be done by a traversal. How much work does a traversal do at each node?
  • Each node is visted once, with constant time spent at each.

Why does function preorder2() presented in the Traversal section make only half as many recursive calls as function preorder()?

  • All nodes will eventually get called
  • The number of nodes in the tree does not change based on the algorithm used to traverse it.
  • The Full Binary Tree Theorem tells us that roughly half of all pointers in a binary tree are null. No recursive call is made for these pointers by preorder2.