 |
| Example binary tree from wikipedia |
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 NoneWe 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 4If 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 3In part-2, I will cover how to automatically insert a new Node and other interesting methods and some common interview questions around binary tree
