Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 8
Exercise 1:
In this exercise the square (nil) nodes in a binary tree are not
considered (counted) and the values stored in the nodes are irrelevant.
- List all binary trees with 3 nodes.
- Find a binary tree with 7 nodes with the longest path from
the root to some leaf.
- Find a binary tree with 7 nodes such that the longest path from
the root to some of the leaves has minimal length.
- Find a binary tree with 9 nodes such that every node which is
not a leaf has exactly two children.
Exercise 2:
Let t be a binary tree.
-
Using only the operations of the ADT binary tree write a function
no_leaves(x:ENTRY_TYPE):int which returns the number of
leaves in the subtree of t rooted by the node x. The tree t
should not be modified.
- What is the worst case complexity of the call no_leaves(t.root)
where the size of the input (number of nodes in t) is denoted
by |t|?
Exercise 3 (hand-in):
Consider a binary tree at the very top of page 110 in the book.
- Write the sequence of visited nodes in preorder traversal.
- Write the sequence of visited nodes in inorder traversal.
- Write the sequence of visited nodes in postorder traversal.
Exercise 4 (hand-in):
Professor Konfus once claimed:
"inorder traversal of a binary tree always visits a leaf as the first node".
Was he right? If yes, prove his claim. If not, give a counter example.
Exercise 5:
What is the worst-case time complexity of preorder(t.root), inorder(t.root)
and postorder(t.root) assuming that visit(x) takes
- O(1) time?
- O(|t|) time?
- O(|t|2*log |t|) time?