# CSC301: Week 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]

• 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"
```

 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.

• 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.

 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.

• no fields.

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

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

Is this correct?

Can it be improved?

```    public int size () {
if (root == null) return 0;
int total = 1 + size (root, 0);
}
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;
}```

Unnecessary else. Tighten mutators.

```    public int size () {
if (root == null) return 0;
int total = 1 + size (root, 0);
}
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;
}```

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

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

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

 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).

 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!

 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

 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