Binary Tree in Python - Part 1

In this post I want to write a little bit about the implementation details of Binary Tree's in my favorite language Python. Before we jump in, conceptually what is a binary tree?  A binary tree is a data structure with a node and each node having at most two child items.

Example binary tree from wikipedia

But wait isn't this a tree?

A tree in real life has trunk, and roots typically in the ground, branches, stems and leaves but in comp science we look at an inverted tree structure, we start with the root and go down to the leaves as shown in the numeric example above. Every circle is called a Node and each Node can have left and right child items.

How to materialize a Node?

In Python, we materialize a Node by defining a class as shown below

class Node(object):
  def __init__(self, data):
    self.data=data
    self.left=None
    self.right=None

Why should we define a class called Node?

Think of this node as our abstract or user defined data type, this is similar to int, float etc. By defining a Node we can leverage the left and right child items which are also of type Node. Remember, everything in Python is an object.  Take for example a variable assignment statement a=1, if you check the type of a we see its of type int, int itself is a class and every class has a constructor so when you create a variable b = int(), this automatically defaults to value zero.

a=1
print type(a)
#

b=int()
print b
#0 

c=int(1)
print c
#1

Going back to our Node class, we can instantiate objects of type Node this way

root=Node(5)
print root.data, root.left, root.right
# 5 None None

We can manually create a Binary tree structure by assigning left and right child items of root node with a variable of type Node

root=Node(5)
print root.data, root.left, root.right
# 5 None None
n4=Node(4)
print n4.data,n4.left,n4.right
# 4 None None 
n3=Node(3)
print n3.data,n3.left,n3.right
# 3 None None
root.left=n3
root.right=n4
print root.data, root.left.data, root.right.data
# 5 3 4

If we examine the type of root.left or root.right we see its an object of class '__main__.Node'. But why should we assign root.left=n3, why can't we say root.left=3? The latter assignment although assigns value three to root's left child its of type int and cannot attach any other Nodes to root.left. Also if you notice, root.left.data and n3.data are same. Originally root.left was None, later we assigned root.left = n3 so root.left is of type Node and hence we can access the data attribute through the dot notation.

print root.left.data, n3.data 
#3 3 

In part-2, I will cover how to automatically insert a new Node and other interesting methods and some common interview questions around binary tree