CSC301: Week 2: Binary Search Trees (3.2)

(Click here for one slide per page)

• Read Algorithms 3.2 on BSTs.

• Read Algorithms 3.1 and 3.5 on symbol tables.

• Complete all of the functions in MyIntSET

• Do the following problems from the text. (Not handed in.)

    3.2.2 
  
      Inserting the keys in the order A X C S E R H into an
      initially empty BST gives a worst-case tree where every node has one
      null link, except one at the bottom, which has two null links. Give
      five other orderings of these keys that produce worst-case trees.
  
      You can also describe the constraints that produce this outcome
           --- Things like "insert A first, insert B before C, etc."
    
    3.2.3
  
      Give five orderings of the keys A X C S E R H that, when
      inserted into an initially empty BST, produce the best-case tree.
    
      You can also describe the constraints that produce this outcome
           --- Things like "insert A first, insert B before C, etc."
  
    3.2.4
  
      Suppose that a certain BST has keys that are integers between
      1 and 10, and we search for 5. Which sequence below cannot be the
      sequence of keys examined? 
  
      a. 10, 9, 8, 7, 6, 5
      b. 4, 10, 8, 6, 5
      c. 1, 10, 2, 9, 3, 8, 4, 7, 6, 5
      d. 2, 7, 3, 8, 4, 5
      e. 1, 2, 10, 4, 8, 5
  
      Typo in the book: (b) should be "4, 10, 8, 7, 5"  not "4, 10, 8, 7, 5, 3" 
  

public class IntSet {
    private Node root;
    private static class Node {
        public final int key;
        public Node left, right;
        public Node (int key) { this.key = key; }
    }
    public int size () {
        int size = 0;
        for (int x : this.levelOrder ())
            size++;
       return size;
    }
    ...

This violates two conditions of the assignment.

• calls function other than the recursive helper function
• creates an object. It is indirect via levelOrder, but it creates an object nonetheless, so it violates the condition of the assignment.

public class IntSet {
    private Node root;
    private static class Node {
        public final int key;
        public Node left, right;
        public Node (int key) { this.key = key; }
    }
    int size = 0;
    public int size () {
        for (int x : this.levelOrder ())
            size++;
       return size;
    }
    ...

This now violates yet another criterion of the assignment.

• no fields.

A field is a variable that is declared outside of a method.

    public int size () {
        return size (root);
    }
    private static int size (Node x) {
        if (x == null) return 0;
        int szl = size (x.left.left) + size (x.left.right) + 1;
        int szr = size (x.right.left) + size (x.right.right) + 1;
        return szl + szr + 1;
    }

Is this correct?

Can it be improved?

    public int size() {
        if (root == null) 
            return 0;
        return 1 + size (root);
    }

    private static int size (Node x) {
        int total = 0;
        if (x == null) 
            return 0;
        if (x.left != null) 
            total += 1 + size (x.left);
        if (x.right != null) 
            total += 1 + size (x.right);
        return total;
    }

Is this correct?

Can it be improved?

    public int size () {
        Node x = root;
        int result = 1;
        return size (x, result);
    }
    private static int size (Node x, int result) {
        if (x.left != null) {
            if (x.right != null) {
                result = +2;
                return size (x.left, result) + size (x.right, result);
            } else {
                result++;
                return size (x.left, result);
            }
        } else if (x.right != null) {
            result++;
            return size (x.right, result);
        } else return result;
    }

Is it correct?

Can it be improved?

    public int size () {
        if (((size (root, 0)) - 1) == -1) return 0;
        return (size (root, 0)) - 1;
    }
    private static int size (Node x, int count) {
        if (x == null) return count;
        else return size (x.left, 1) + size (x.right, 1);
    }

Is it correct?

Can it be improved?

    public int size () {
        if (root == null) return 0;
        return size (root) - 1;
    }
    private static int size (Node x) {
        if (x == null) return 1;
        return size (x.left) + size (x.right);
    }

Cleaned up

Counts the number of nulls, rather than the number of nodes.

Correct, but not immediately obvious.

    public int size () {
        return size (root);
    }
    private static int size (Node x) {
        if (x == null) return 0;
        if (x.left == null && x.right == null) return 1;
        if (x.left == null && x.right != null) return size (x.right) + 1;
        if (x.left != null && x.right == null) return size (x.left) + 1;
        else return size (x.left) + size (x.right) + 1;
    }

Is it correct?

Can it be improved?

    public int size () {
        return size (root);
    }
    private static int size (Node x) {
        int count = 0;
        if (x == null) return 0;
        if (x.left == null && x.right == null) {
            count = 1;
        } else {
            count = 1 + size (x.left) + size (x.right);
        }
        return count;
    }

Is it correct?

Can it be improved?

    public int size () {
        if (root == null) return 0;
        int total = 1 + size (root, 0);
        return total; // do not count self at the start
    }
    private static int size (Node x, int count) {
        // called when it finds the end
        int total = count, left = 0, right = 0; // likely can use less space - see about condensing
        if (x == null) return 0; // return 0 when the node is null - thus finding the end!
        else { // not at the end when this is called
            // if left has more, add them up and return them
            if (x.left != null) {
                left++; // increment
                left += size (x.left, left); // should add...
            }
            if (x.right != null) {
                right++;
                right += size (x.right, right);
            }
            // if right has more, add them up and return them
        }
        total = left + right;
        // return result
        return total;
    }

Is this correct?

Can it be improved?

Get rid of comments:

    public int size () {
        if (root == null) return 0;
        int total = 1 + size (root, 0);
        return total;
    }
    private static int size (Node x, int count) {
        int total = count, left = 0, right = 0;
        if (x == null) return 0;
        else {
            if (x.left != null) {
                left++;
                left += size (x.left, left);
            }
            if (x.right != null) {
                right++;
                right += size (x.right, right);
            }
        }
        total = left + right;
        return total;
    }

Unnecessary else. Tighten mutators.

    public int size () {
        if (root == null) return 0;
        int total = 1 + size (root, 0);
        return total;
    }
    private static int size (Node x, int count) {
        int total = count, left = 0, right = 0;
        if (x == null) return 0;
        if (x.left != null) left += 1 + size (x.left, left);
        if (x.right != null) right += 1 + size (x.right, right);
        total = left + right;
        return total;
    }

Get rid of some unnecessary variables and put declaration closer to use.

    public int size () {
        if (root == null) return 0;
        return 1 + size (root, 0);
    }
    private static int size (Node x, int count) {
        if (x == null) return 0;
        int total = count;
        if (x.left != null) total += 1 + size (x.left, left);
        if (x.right != null) total += 1 + size (x.right, right);
        return total;
    }

Oops! A bug.

    public int size () {
        if (root == null) return 0;
        return 1 + size (root, 0);
    }
    private static int size (Node x, int count) {
        if (x == null) return 0;
        int total = 0;
        if (x.left != null) total += 1 + size (x.left, left);
        if (x.right != null) total += 1 + size (x.right, right);
        return total;
    }

Notice that the parameter is not used!

    public int size () {
        if (root == null) return 0;
        return 1 + size (root);
    }
    private static int size (Node x) {
        if (x == null) return 0;
        int total = 0;
        if (x.left != null) total += 1 + size (x.left);
        if (x.right != null) total += 1 + size (x.right);
        return total;
    }

    public void putLeft (int key) {
        if (root==null) {
            root = new Node (key);
        } else {
            Node x = root;
            while (x != null) {
                x = x.left;
            }
            x = new Node (key);
        }
    }

Warmup with put left, which adds a new minimum element.

Is this correct?

    public void putLeft (int key) {
        if (root==null) {
            root = new Node (key);
        } else {
            Node x = root;
            while (x.left != null) {
                x = x.left;
            }
            x = new Node (key);
        }
    }

Is this correct?

    public void putLeft (int key) {
        if (root==null) {
            root = new Node (key);
        } else {
            Node x = root;
            while (x.left != null) {
                x = x.left;
            }
            x.left = new Node (key);
        }
    }

    public void putLeft (int key) {
        if (root==null) {
            root = new Node (key);
        } else {
            putLeft (root, key);
        }
    }
    private static void putLeft (Node x, int key) {
        if (x.left == null)
            x.left = new Node (key);
        else {
            putLeft (x.left, key);
        }
    }

Make it recursive.

    public void put (int key) {
        if (root==null) {
            root = new Node (key);
        } else {
            put (root, key);
        }
    }
    private static void put (Node x, int key) {
        if (key < x.key) {
            if (x.left == null)
                x.left = new Node (key);
            else
                put (x.left, key);
        } else if (key > x.key) {
            if (x.right == null)
                x.right = new Node (key);
            else
                put (x.right, key);
        }
    }

Left and right.

Wow. Too many base cases!

Single method call responsible both for creating the node and for putting it in the right place.

    public void put (int key) {
        root = put (root, key);
    }
    private static Node put (Node x, int key) {
        if (x == null) return new Node (key);
        //...
    }

To get rid of too many base cases, we must embrace null.

One method call responsible for creating the node.

A different method call responsible for putting it in the right place.

This works if we insert one key into the empty tree

    public void put (int key) {
        root = put (root, key);
    }
    private static Node put (Node x, int key) {
        if (x == null)
            return new Node (key);
        if (key < x.key)
            put (x.left,  key);
        else if (key > x.key)
            put (x.right, key);
        //...
    }

This is kind of what we want.

Does it work?

    public void put (int key) {
        root = put (root, key);
    }
    private static Node put (Node x, int key) {
        if (x == null)
            return new Node (key);
        if (key < x.key)
            x.left  = put (x.left,  key);
        else if (key > x.key)
            x.right = put (x.right, key);
        // what do I return here?
    }

Try inserting two things into an empty tree.

We need to remember the root.

    public void put (int key) {
        root = put (root, key);
    }
    private static Node put (Node x, int key) {
        if (x == null)
            return new Node (key);
        if (key < x.key)
            x.left  = put (x.left,  key);
        else if (key > x.key)
            x.right = put (x.right, key);
        return x;
    }

Here is the final code.

Software engineering: Once and only once. This code is much better than the look before you leap that we started with. (See also here).

Software engineering: Refactoring. Changing the structure of code without changing its meaning. (See also here).

Possible performance issue: we are re-assigning the fields in the tree as we go up. This work is not done by look before you leap approach.

Software engineering wins! Premature optimization is the source of many bugs!

    public void printPre () {
        printPre (root, 0);
    }
    private static void printPre (Node x, int d) {
        if (x == null) return;
        indent (d);
        StdOut.println (x.key);
        printPre (x.left, d+1);
        printPre (x.right, d+1);
    }
    private static void indent (int d) {
        for (int i=0; i<d; i++)
            StdOut.print ("  ");
    }

This is Pretty Printing where we use indentation to show depth.

    public void printPre () {
        printPre (root);
        StdOut.println ();
    }
    private static void printPre (Node x) {
        if (x == null) return;
        StdOut.print (x.key + " ");
        printPre (x.left);
        printPre (x.right);
    }

Print prefix (simple version).

What about infix? postfix?

    public void printIn () {
        printIn (root);
        StdOut.println ();
    }
    private static void printIn (Node x) {
        if (x == null) return;
        printIn (x.left);
        StdOut.print (x.key + " ");
        printIn (x.right);
    }

Yeah!

    public void printPost () {
        printPost (root);
        StdOut.println ();
    }
    private static void printPost (Node x) {
        if (x == null) return;
        printPost (x.left);
        printPost (x.right);
        StdOut.print (x.key + " ");
    }

Yeah!

What about using a loop?

    public void printPre () {
        Stack<Node> s = new Stack<> ();
        s.push (root);
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null) continue;
            StdOut.print (x.key + " ");
            s.push (x.right);
            s.push (x.left);
        }
        StdOut.println ();
    }

Print prefix with a loop

Not so bad.

    public void printPost () {
        Stack<int>  r = new Stack<> ();  // keys to print out
        Stack<Node> s = new Stack<> ();  // nodes for the traversal
        s.push (root);
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null) continue;
            r.push (x.key);
            s.push (x.left);
            s.push (x.right);
        }
        while (!r.isEmpty ())
            StdOut.print (r.pop () + " ");
        StdOut.println ();
    }

Print postfix with a loop

Hmmm.

    public void printIn () {
        Stack<Node> s = new Stack<> ();
        Node x = root;
        while (x != null || !s.isEmpty ()) {
            if (x != null) {
                s.push (x);
                x = x.left;
            } else {
                x = s.pop ();
                StdOut.print (x.key + " ");
                x = x.right;
            }
        }
        StdOut.println ();
    }

Print infix with a loop (from here)

Yeesh.

    public void printPost () {
        Stack<Node> s = new Stack<>();
        s.push (root);

        Node prev = root;
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null) continue;
            if (x.right == prev || x.left == prev || (x.left == null && x.right == null)) {
                StdOut.print (x.key + " ");
                prev = x;
            } else {
                s.push (x);
                s.push (x.right);
                s.push (x.left);
            }
        }
        StdOut.println ();
    }

Print postfix with only one loop (from here and here)

Horror.

    public void printPre () {
        Stack<Node> s = new Stack<> ();
        s.push (root);
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null) continue;
            StdOut.print (x.key + " ");
            s.push (x.right);
            s.push (x.left);
        }
        StdOut.println ();
    }

Print level-order in a loop: not bad

    public void printLevel () {
        Queue<Node> q = new Queue<> ();
        q.enqueue (root);
        while (!q.isEmpty ()) {
            Node x = q.dequeue ();
            if (x == null) continue;
            StdOut.print (x.key + " ");
            q.enqueue (x.left);
            q.enqueue (x.right);
        }
        StdOut.println ();
    }

Print level-order in a loop: not bad

Postfix and infix are bad.

Revised: 2008/03/17 13:01