title: recursive class definition in python
body: <p>Sorry if my English is bad, I speak Korean as mother tongue.<br />
  I am implementing binary search tree in Python 3, but I wasn't able to meet my goal.<br />
  Here is code:</p>
  <pre><code>class Node(object):
  
      def __init__(self, key=None, data=None):
          self.key = key
          self.data = data
  
  class BinarySearchTree(object):
      keyfunc = None  # Will it be worse when using lambda x: x as default?
      
      def __init__(self, node=None):
          self.root = node
          self.left = None
          self.right = None
          # I don't want default to be NoneType, but don't know how for now.
  
      def add(self, key, data=None):
          node = Node(key, data)
          if self.root is None:
              self.root = node
              return
          parent = self.root.key
          if self.keyfunc is None:
              if key &lt; parent:
                  if self.left is None:
                      self.left = __class__(node)
                  else:
                      self.left.add(key, data)
                          
              elif key &gt; parent:
                  if self.right is None:
                      self.right = __class__(node)
                  else:
                      self.right.add(key, data)
          else:
              if keyfunc(key) &lt; keyfunc(parent):
                  if self.left is None:
                      self.left = __class__(node)
                  else:
                      self.left.add(key, data)
              elif keyfunc(key) &gt; keyfunc(parent):
                  if self.right is None:
                      self.right = __class__(node)
                  else:
                      self.right.add(key, data)
      def inorder(self):
          if self.root:
              if self.left:
                  self.left.inorder()
              print(self.root.key, end=' ')
              if self.right:
                  self.right.inorder()
  
  if __name__ == '__main__':
      bst1 = BinarySearchTree()
      arr = [2,6,4,3,2,7,8,1,9,5]
      for key in arr:
          bst1.add(key)
      bst1.inorder()
  </code></pre>
  <p>It works anyway, but what I want is:</p>
  <ul>
  <li>even when root node has no child, I want the type of <code>bst1.left</code>(or <code>bst1.right</code>) be always BinarySearchTree.<br />
  That way, I can allow null tree treated in consistency with other trees, and also can I remove repeating <code>if self.left is None</code> in add().</li>
  <li>I don't want to manually do <code>bst1.left = BinarySearchTree(None)</code> after class definition, because it will be required to applied to all of nodes.</li>
  </ul>
  <p>I tried <code>self.left = BinarySearchTree(None)</code>(of course it resulted bad recursion),
  and tried to use <code>__new__()</code> method and Metaclasses as answered in other stackoverflow questions, but couldn't come up with solution.<br />
  It would very grateful if I can get help.</p>