Art in New York City

Being from Seattle, I found myself delighted at the chance to poke fun at the art scene in New York.

I love Seattle, but why poke fun at Seattle artists with a comic when New York artists are practically cartoon characters already?

Parentless Binary Search Tree

Binary search tree's are a helpful data structure in which nodes have two children and one parent. A nodes left child will be less then the parent, and a nodes right child will be more then the parent. In a BST where nodes have no parent pointer, every node is essentially its own tree. This means any method that you can call on a tree head, you can call on it's children, allowing for recursive solutions to most BST problems or methods.
Node insertion is easy, with or without a parent pointer.

...
  def insert(self, val):
      if val < self.val:
          if self.lchild is None:
              self.lchild = TreeNode(val)
          else:
              self.lchild.insert(val)
      if val > self.val:
          if self.rchild is None:
              self.rchild = TreeNode(val)
          else:
            self.rchild.insert(val)

Traversal is also easy.

...
  def depth_traversal(self, order="pre"):
      if order == "pre":
          yield self.val
      if self.lchild is not None:
          for v in self.lchild.depth_traversal(order=order):
              yield v
      if order == "in":
          yield self.val
      if self.rchild is not None:
          for v in self.rchild.depth_traversal(order=order):
              yield v
      if order == "post":
          yield self.val

These are simple, because you are recursing down the tree.
Tree balancing is much more complicated, because logically you need to start on the bottom of the tree, each node rotation needs to update what the parent is pointing to, and the pointer to the head node may no longer be the head node.
All of these problems can be worked around. If you return the pivot node at the end of a rotation, then you can call rotations from the parents pointer.

    def _rot_right(self):
        pivot = self.lchild
        self.lchild.rchild, self.lchild = self, self.lchild.rchild
        return pivot

    def _rot_left(self):
        pivot = self.rchild
        self.rchild.lchild, self.rchild = self, self.rchild.lchild
        return pivot

>>> node.lchild = node.lchild._rot_right()

Starting at the bottom of the tree can work in the same way as post oder traversal, where by recursing through the tree at the beginning of your function, and stepping through logic after assures that you will visit all the children of a node before you visit that node

...
  def rebalance(self, head):
    if self.lchild is not None:
        self.lchild.rebalance(head=head)
    if self.rchild is not None:
        self.rchild.rebalance(head=head)

    balance = self.balance()
    if balance > 1:
        lbalance = self.lchild.balance()
        if lbalance > 1:
            self.lchild = self.lchild._rot_right()
        elif lbalance < -1:
            self.lchild = self.lchild._rot_left()
    elif balance < -1:
        rbalance = self.rchild.balance()
        if rbalance > 1:
            self.rchild = self.rchild._rot_right()
        elif rbalance < -1:
            self.rchild = self.rchild._rot_left()

Rebalancing should return the new head node, so that pointers can be reassigned elsewhere.

...
  if head is self:
      if balance > 1:
          head = self._rot_right()
          head = head.rebalance(head)
          return head
      elif balance < -1:
          head = self._rot_left()
          head = head.rebalance(head)
          return head
    return self

And there you have it. A Binary Search Tree with no parent pointer.