12.1

12.1-1

For the set of {1; 4; 5; 10; 16; 17; 21} of keys, draw binary search trees of heights 2,3, 4, 5, and 6.

Solution:

Binary Search Tree with Height 2

Binary Search Tree with Height 3

Binary Search Tree with Height 4

Binary Search Tree with Height 5

Binary Search Tree with Height 6

12.1-2

What is the difference between the binary-search-tree property and the min-heap property (see page 153)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Show how, or explain why not.

Solution

In a min-heap, the invariant is that the parent node should be smaller than the child nodes. There is no ordering maintained between the left and right child of the node. The left child can be > or < parent and the same holds true for the right child.However we can run the Heap sort algorithm on a min heap to get the sorted keys. But that would cost O(n log n).

On the other hand, a BST maintains an invariant where left subtree <= node and the right tree > node. This allows a BST to return sorted keys when the in order traversal is performed on the tree. The in order traversal visits the nodes in the following order:

Left -> Node -> Right

12.1-3

Give a non recursive algorithm that performs an in order tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant,solution uses no stack but assumes that we can test two pointers for equality.

Solution

12.1-4

Give recursive algorithms that perform preorder and postorder tree walks in ѳ(n)time on a tree of n nodes.

Solution: Algorithm for Preorder Walk is shown below.

preorder(Node root){

 if(root != null){

      Print root.value;

     preorder(root.left);

    preorder(root.right);

  }}

Algorithm for Postorder walk is shown below:

postorder(Node root){

 if(root != null){

     preorder(root.left);

    preorder(root.right);

    Print root.value;

  }}

Both of the algorithms having a running time ѳ(n).

12.1-5

Argue that since sorting n elements takes Ω(n lg n) time in the worst case in the comparison model, any comparison-based algorithm for constructing a binary search tree from an arbitrary list of n elements takes Ω(n lg n) time in the worst case

Solution:

To build a Binary Search Tree using a list of length n, it takes Ω(n lg n). Now why does it take that long? The cost of each insert is Ω(log n) based on key comparisons and this comparison is performed for n elements, so the total cost becomes Ω(n lg n). However, the cost of insert can be O(n) if the list is already sorted, thus making the total cost of building the BST O(n^2). If it was possible to build a BST in time less than Ω(n lg n), then there would have existed some comparison based model that had a running better than Ω(n lg n). Since the worst case running time of sorting takes Ω(n lg n), it would be the same for building a BST too.