Objectives: Understanding trees, BSTs, AVL Trees.
Problem 1 --- Tree traversals: [10 Points, 5pts. each]
A. Draw a single binary tree, where each internal node stores one character, such that a preorder traversal yields E X A M F U N and when an inorder traversal is performed it prints M A F X U E N.
B. Draw every possible binary tree that stores a single integer and when traversed inorder prints 10, 5, 8, 9.
Problem 2:[10 Points]
Two nonempty ordered trees, T and T' are said to be isomorphic if one of the following holds:
Design an algorithm (in pseudocode) to test whether two trees are isomorphic. What is the running time of this algorithm (Big O)?
Problem 3:[10 Points]
Show by induction that the number of degree-2 nodes in any nonempty binary tee is 1 less than the number of leaves.
Problem 4:[10 Points]
Show that if a node in a binary search tree has two children then its successor has no left child and its predecessor has no right child.
Problem 5:[10 Points]
Give a sequence of 10 keys (Use letters A through J) that when inserted into an initially empty binary search tree via the root insertion method, requires a maximal number of comparisons to build the tree. Give the number of comparisons needed.
Problem 6:[10 Points]
Draw step by step the AVL tree that results when you insert items with the keys E, A, S, Y, Q, U, T, I, O, N in that order into an intially empty tree.
Problem 7:[10 points]
Give an algorithm (in pseudocode) which determines whether a given binary tree is a binary search tree. What is its running time in Big O notation?