COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

Review Questions — Trees

General Trees

First-Child, Next-Sibling Representation

1. Draw the general tree that corresponds to the following first-child, next-sibling representation of a tree.

   Imagine some binary tree diagram here.

Tree Traversal Algorithms

1. Suppose we have three functions preorder( n, T ), inorder( n, T ), and postorder( n, T ) that give the preorder, inorder, and postorder positions, respectively, of node n in tree T. How can we determine whether node i is an ancestor of node j using these functions? [Note: "ancestor", not "proper ancestor".]

2. Indicate the order in which the nodes of the following tree would be visited by (a) a preorder traversal and (b) a postorder traversal.

   

Binary Trees

1. What is the difference between a binary tree and a general tree with a maximum of two children per node?

2. Draw a (single) binary tree T such that

   1. Each internal node of T stores a single character.

   2. A preorder traversal of T yields EXAMFUN.

   3. An inorder traversal fo T yields MAFXUEN.