CSC301: Lecture 2 (Binary Search Trees (3.2))

Contents [0/30]

Homework [1/30]
More Size: Using a built in iterator [2/30]
More Size: How is this different? [3/30]
More Size: Student code [4/30]
More Size: Student code [5/30]
More Size: Student code [6/30]
More Size: Student code [7/30]
More Size: Student code [8/30]
More Size: Student code [9/30]
More Size: Student code [10/30]
More Size: Student code [11/30]
Put: Starter code [12/30]
Put: Get to the right place [13/30]
Put: Remember what you've made [14/30]
Put: Recursive [15/30]
Put: Left and Right [16/30]
Put: Embrace null [17/30]
Put: Don't forget your children! [18/30]
Put: One last question [19/30]
Put: Reassigning as we go back up [20/30]
Printing: Print prefix [21/30]
Printing: Print prefix [22/30]
Printing: Print infix [23/30]
Printing: Print postfix [24/30]
Printing: Print prefix with a loop [25/30]
Printing: Print postfix with a loop [26/30]
Printing: Print infix with a loop [27/30]
Printing: Print postfix with only one loop [28/30]
Printing: Print prefix with a loop [29/30]
Printing: Print level-order in a loop [30/30]

Homework [1/30]

More Size: Using a built in iterator [2/30]

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.

More Size: How is this different? [3/30]

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.

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

More Size: Student code [4/30]

    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?

More Size: Student code [5/30]

  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?

More Size: Student code [6/30]

    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?

More Size: Student code [7/30]

    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?

More Size: Student code [8/30]

    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.

More Size: Student code [9/30]

    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?

More Size: Student code [10/30]

    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?

More Size: Student code [11/30]

    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;
    }

Put: Starter code [12/30]

    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?

Put: Get to the right place [13/30]

    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?

Put: Remember what you've made [14/30]

    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);
        }
    }

Put: Recursive [15/30]

    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.

Put: Left and Right [16/30]

    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.

Put: Embrace null [17/30]

    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

Put: Don't forget your children! [18/30]

    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?

Put: One last question [19/30]

    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.

Put: Reassigning as we go back up [20/30]

    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!

Printing: Print prefix [21/30]

    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.

Printing: Print prefix [22/30]

    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?

Printing: Print infix [23/30]

    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!

Printing: Print postfix [24/30]

    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?

Printing: Print prefix with a loop [25/30]

    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.

Printing: Print postfix with a loop [26/30]

    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.

Printing: Print infix with a loop [27/30]

    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.

Printing: Print postfix with only one loop [28/30]

    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.

Printing: Print prefix with a loop [29/30]

    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

Printing: Print level-order in a loop [30/30]

    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