Tree Drawing

A good tree drawing should have the following properties:

  1. Every node should have a unique x coordinate
  2. All of the nodes in the left subtree of a particular node should be to the left of that node. Similarly, all of the nodes in the right subtree of a particular node should be to the right of that node
  3. The y coordinates of the nodes should be proportional to their "depth" (i.e. the length of the shortest path from the root to that node, or as how many recursive calls you need to reach that node, starting at the root)
In [1]:
# import numpy as np
import matplotlib.pyplot as plt

class TreeNode(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    
    def draw(self, width, x, depth):
        y = -depth
        # Draw a dot
        plt.scatter([x], [y], 50, 'k')
        # Draw some text indicating what the value is
        plt.text(x+width*0.05, y, "{}".format(self.value))
        # Offset in x
        dx = width/2**depth        
        if self.left:
            xnext = x - dx
            # Draw a line segment from my node to this left child
            plt.plot([x, xnext], [-depth, -depth-1])
            self.left.draw(width, xnext, depth+1)
        if self.right:
            xnext = x + dx
            # Draw a line segment from my node to this left child
            plt.plot([x, xnext], [-depth, -depth-1])
            self.right.draw(width, xnext, depth+1)
    
    def inorder(self):
        if self.left:
            self.left.inorder()
        print(self.value, end=" ")
        if self.right:
            self.right.inorder()
        

class BinaryTree(object):
    def __init__(self):
        self.root = None
    
    def draw(self, width):
        if self.root:
            self.root.draw(width, 0, 0)
        plt.axis("off")
        plt.axis("equal")
    
    def inorder(self):
        if self.root:
            self.root.inorder()

def make_left_subtree():
    node = TreeNode(7)
    node.left = TreeNode(3)
    node.right = TreeNode(9)
    node.right.left = TreeNode(8)
    return node

def make_right_subtree():
    node = TreeNode(16)
    node.left = TreeNode(11)
    node.right = TreeNode(20)
    node.left.right = TreeNode(14)
    node.left.right.right = TreeNode(15)
    node.left.right.left = TreeNode(13)
    node.left.right.left.left = TreeNode(12)
    return node

def make_tree():
    T = BinaryTree()
    T.root = TreeNode(10)
    T.root.left = make_left_subtree()
    T.root.right = make_right_subtree()
    return T

T = make_tree()
T.draw(5)

Property 2 is the hardest to prove that we satisfied, but we can see this by the fact that the amount that we move left/right to a child is halved each time the depth increases. This means that if we move by an amount $w$ to the right, for example, it's impossible for us ever to move all the way back to the left, because we can move by

$w/2 + w/4 + w/8 + ... + w/2^d < w$

Binary Search Trees (BST)

A BST is a binary tree with the property that all of the values in a node's left subtree are $<$ than the node's value, while all of the values in a node's right subtree are $>$ that node's value

Corollary: Left child of a node has a value $<$ this value, and the right child has a value $>$ the node's value

Lemma: The inorder traversal of a BST will yield the values in sorted order

In [2]:
T.inorder()

3 7 8 9 10 11 12 13 14 15 16 20
In [ ]: