What is Binary Tree?

Trees are a very important part of the data structure. Either you want to be a good programmer or just want to have a basic understanding of Data Structures, you need to understand basic concepts of trees. There are various types of trees but binary tree is one of the most widely used and easy to implement data structure tree. It is most efficient for searching and information retrieval. In this post I will cover various properties, types and traversal of Binary tree.

Average time complexity of a binary tree is only O(log n) and its space complexity is O(n). As the name suggests each node has at most 2 children. Each child is either designated as left child or right child. The first node is root node and does not have any parent and the last node is called as leaf node. Leaf node doesn't have any child node and it points to null. Binary tree is used to implement binary search trees (BST) and various other trees which are based on the binary structure.  

Properties of Binary Tree:

• Maximum no of nodes on any level x is 2^x (root level is 0).
• Maximum no of nodes possible in a binary tree of height h is 2^h-1.
• Minimum no of nodes in a binary tree of height h is h.
• If n nodes in a tree the maximum height possible is n and minimum height possible is log2(n+1).
• Total no of edges, e, if n nodes - e=n-1.

Types Of Binary Trees:

Degenerate Binary tree: Tree in which each node has only one child node. This tree behaves like a linked list. Its height is O(n) for n nodes. This is the worst case of BST.

Strictly Binary Tree or 2 - Tree or Full binary tree: A tree in which each node is either a leaf node or has exactly 2 child nodes.

Complete Binary tree: A tree in which all levels, except the last, is completely filled and all the nodes are towards the left.

Perfect Binary Tree: All leaves are at the same depth i.e. It is perfect in the sense that no node has either one or 0 child except the last one and the depth(height) of left and right child on each level is equal(not to be confused with complete or strict binary tree). 

After having a basic understanding of what are the different types of trees and their properties let’s see how to do a binary tree traversal?

Traversal: 
There are 3 ways of binary tree traversal :

Preorder Traversal (NLR): 

• Visit the root (N).
• Then traverse the left child of the root node (L).
• At last traverse the right child of the root node (R). (See Example)

Inorder Traversal (LNR): 

• Visit the left child of the root node (L).
• Then traverse the root node (N).
• At last traverse the right child of the root node (R).

Postorder Traversal (LRN):

• Visit the left child of the root node (L).
• Then traverse the right child of root node (R).
• At last traverse the root node (N).

Example:

Preorder Traversal:  10 5 2 30 25 45

Inorder Traversal: 2 5 10 25 30 45

Postorder Traversal:  2 5 25 45 30 10

Now you have a good understanding of binary tree. In next tutorials I will cover Binary Search Trees and various other trees. 
If you have any difficulties please comment and I will try my level best to sort it out.