Binary Tree

A Binary tree is a data structure that stores the data hierarchically in the form of a tree. Each node of a binary tree has 2 pointers usually called left and right. Additionally , the nodes can contain other types of data. For example, a binary tree of integers could be made up of objects of the following type:

struct tree {

int item; // The data in this node.

tree * left; // Pointer to the left subtree.

tree * right; // Pointer to the right subtree.

}



Binary Tree



The top most node of a tree is called the "root" node. A tree always starts from the root. The left and right pointers in a TreeNode can point to one,two or no nodes. A node that points to another node is said to be the parent of that node, and the node it points to is called a child. In the given picture , for example, node 7 is the parent of node 6, and nodes 5 and 11 are children of node 6. Not every linked structure made up of tree nodes is a binary tree.

A binary tree must have the following properties: There is exactly one node in the tree which has no parent. This node is called the root of the tree. Every other node in the tree has exactly one parent. Finally, there can be no loops in a binary tree. That is, it is not possible to follow a chain of pointers starting at some node and arriving back at the same node. A node that has no children is called a leaf or a terminal node. A leaf node has both the left and right pointers as null. In the standard picture of a binary tree, the root node is shown at the top and the leaf nodes at the bottom.

Consider any node in a binary tree. Look at that node together with all its descendents (that is, its children, the children of its children, and so on). This set of nodes forms a binary tree, which is called a subtree of the original tree. For example, in the picture, nodes 7, 2, and 6 form a subtree. This subtree is called the left subtree of the root. Similarly, nodes 5 and 9 make up the right subtree of the root. We can consider any non-empty binary tree to be made up of a root node, a left subtree, and a right subtree. Either or both of the subtrees can be empty. This is a recursive definition, matching the recursive definition of the TreeNode class.

Traversing a binary tree

There are three methods by which a binary tree can be traversed :

1. Preorder : In this type of traversal the root nodes is processed first following by left and right nodes. For example, in the above picture, between 2, 7 and 5, the preorder method will read 2 first, followed by 7 and 5.
2. Postorder : In a postorder traversal, the left subtree is traversed, then the right subtree, and then the root node is processed. In this method of reading 7,5 and 2 will be printed.
3. Inorder : In an inorder traversal, the left subtree is traversed first, then the root node is processed, then the right subtree is traversed. The output for the same set of nodes will be 7,2 and 5.