Kashish Dugar

Today I built a binary search tree from scratch.

The rule

Every node has a value, a left and a right. Smaller numbers go left and bigger numbers go right, like a number line: 0123456789, where the small ones are on the left. The top node is called the root.

I drew it on paper first: 5 at the top, 3 on the left, 8 on the right, and 1 under the 3.

Insert

To insert, you start at the root and keep going left or right until you find an empty spot. My first try put the new node straight under the root, but then the 3 got lost! So I added a while True loop that keeps moving down until it finds None.

def insert(self,value):
        new_node = Node(value)
        if self.root == None:
            self.root = new_node
        else:
            current = self.root
            while True:
                if value < current.value:
                    if current.left == None:
                        current.left = new_node
                        return new_node
                    else:
                        current = current.left
                else:
                    if current.right == None:
                        current.right = new_node
                        return new_node
                    else:
                        current = current.right

Inorder

Inorder means left, then the node, then right. My tree printed 1, 3, 5, 8, which is sorted! That happens because everything on a node’s left is smaller, so it always prints first.

def inorder(self, node):
        if node is None:
            return

        self.inorder(node.left)
        print(node.value)
        self.inorder(node.right)

Also today

I traced fact(4) on paper with a call stack and got 24. The last call finishes first.

I also read Petzold Chapter 6. Switches in series are AND, and switches in parallel are OR. In Boole’s algebra 1 + 1 = 1. It’s like having two red Ferraris: it’s still just “yes, red.”