Tree nodes

Just as was the case with other data structures that we encountered, such as lists and stacks, trees are built up of nodes. But the nodes that make up a tree need to contain data about the parent-child relationship that we mentioned earlier.

Let us now look at how to build a binary tree node class in Python:

    class Node: 
        def __init__(self, data): 
            self.data = data 
            self.right_child = None 
            self.left_child = None 

Just like in our previous implementations, a node is a container for data and holds references to other nodes. Being a binary tree node, these references are to the left and the right children.

To test this class out, we first create a few nodes:

    n1 = Node("root node")  
    n2 = Node("left child node") 
    n3 = Node("right child node") 
    n4 = Node("left grandchild node") 

Next, we connect the nodes to each other. We let n1 be the root node with n2 and n3 as its children. Finally, we hook n4 as the left child to n2, so...