HW3

Due July 24

70 Points

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:

    1. T and T' consist of a single node.
    2. T and T' have the same number k of subtrees and the ith subtree of T is isomorphic to the ith subtree of T', for i = 1, 2, ... , k.

    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?