CSC403: Trees: Put

Contents [0/9]

Put: Starter code [1/9]
Put: Get to the right place [2/9]
Put: Remember what you've made [3/9]
Put: Recursive [4/9]
Put: Left and Right [5/9]
Put: Embrace null [6/9]
Put: Don't forget your children! [7/9]
Put: One last question [8/9]
Put: Reassigning as we go back up [9/9]

(Click here for one slide per page)


Put: Starter code [1/9] 

    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 [2/9] 

    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 [3/9] 

    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 [4/9] 

    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 [5/9] 

    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 [6/9] 

    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! [7/9] 

    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 [8/9] 

    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 [9/9] 

    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.
Generalization of: Don't Repeat Yourself! (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!