In linear data structures, data items are stored in a sequential order, one after another, whereas nonlinear data structures store data items in a non-linear order, where a data item can be connected to more than one data item. All of the data items in the linear data structures can be traversed in one pass, whereas this is not possible in the case of a non-linear data structure. The trees are the non-linear data structure; they store the data differently from other linear data structures such as arrays, lists, stacks, and queues.

In the tree data structure, the nodes are arranged in a parent-child relationship. There should not be any cycle among the nodes in trees. The tree structure has nodes to form a hierarchy, and a tree that has no node is called an empty tree.

First, we will discuss one of most important and special kinds of trees available, that is, the binary tree. A binary tree is a collection of nodes, where the nodes in the tree can have zero, 1, or 2 child nodes. A simple binary tree has a maximum of two children, that is, the left child and the right child. For example, in the following binary tree example, there is a root node that has two children (left child, right child):

A tree is called a full binary tree if all the nodes of a binary tree have either zero or two children, and if there is no node that has 1 child. A binary tree is called a complete binary tree if it is completely filled, with a possible exception at the bottom level, which is filled from left to right.

Just like in our previous implementations, a node is a container for data and holds references to other nodes. In a binary tree node, these references are to the left and the right children. Let's look at the following code for building a binary tree node class in Python:

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

To test this class, we must first create four nodes—n1, n2, n3, and n4:

    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 according to the property of a binary tree. We let n1 be the root node, with n2 and n3 as its children. Finally, we take n4 as the left child to n2. Take a look at the following diagram to see how we connect these nodes to each other:

The next code snippet should be following in order to connect the nodes to each other according to the preceding diagram: 

    n1.left_child = n2 
    n1.right_child = n3 
    n2.left_child = n4 

Here, we have set a very simple tree structure of four nodes. The first important operation that we would like to perform on trees is traversal. To understand traversing, let's traverse the left sub-tree of this binary tree. We will start from the root node, print out the node, and move down the tree to the next left node. We keep doing this until we have reached the end of the left sub-tree, like so:

    current = n1 
    while current: 
        print(current.data) 
        current = current.left_child 

The output of traversing the preceding code block is as follows:

root node 
left child node 
left grandchild node