A binary tree is a tree data structure which stores items in a hierarchical format. Each item is stored in a node which can contain upto two child nodes. Each child node can in turn store another item and can have upto two more child nodes.
Anatomy of a Binary Tree
A binary tree is composed of multiple nodes. Each node can store data of any item and can also store links/pointers to a maximum of two child nodes. The node from which we start looking for data is termed as the root node of a binary tree. Below is how a binary tree looks like:
In the binary tree illustrated above, the node which stores value A is the root node. This is the node from which we start traversing other nodes in the tree. The root node A has a connection to another child node B towards it’s left. So node B is called as the left node of node A. Similarly the root node A has a connection to another child node C towards its right. So node C is called as the right child node of node B.
The node B has link to a right child node D and another link to left child node E. But if we look at the node C, it has link to only left child node F. Node C doesn’t link or point to any right child node. Any node in a binary tree which does not contain left and right children is known as a leaf node. In the example above, nodes D, E, F do not have links to left or right childs and so they are called as leaf nodes.
Also, Nodes B and C, which are not root nodes or leaf nodes are called as internal nodes.
Depth of any node in a Binary Tree
The depth of any node in a binary tree is the number of links between the node and the root node. For example, between the left node of the root node and root node, there is only one link. So the depth of the left node is 1. For root node, there are no links with itself, so it’s depth is 0. Below is an example binary tree with the depths marked for each node.
Between node C and root node A, there is one link. So the depth of node C is 1. Similarly between node F and root node A, there are 2 links. So the depth of node F is 2.
Height of any node in a Binary Tree
The height of node in a binary tree is the maximum number of links present between the node and any leaf node connected to it. Below is an example binary tree with heights marked for each node.
The height of the root node will be the maximum number of links between the root node and any child node connected to it. In the above tree, node G is the farthest leaf node and there are 3 links between node G and root node A. So the height of root node A is 3. Similarly for node B, the farthest leaf node connected to it are nodes D or E and there is only 1 link between them. So the height of node B is 1.
Types of Binary Trees
Full Binary Trees
A full binary tree is a binary tree in which each node either has 2 child nodes or no child nodes at all. For example the below binary tree is a kind of full binary tree (source). There are no nodes in the tree which has only one child. Every node either has 2 child nodes or no nodes at all.
Complete Binary Tree
A complete binary tree is a binary tree in which all the rows/layers are completely filled except possibly for the last row. In the last row, the nodes should be continuously filled from left to right. For example, the binary tree illustrated below is a complete binary tree.
Where as the binary tree shown below is not complete since in the last row, the nodes towards left are not continuous i.e., there is a gap between node D and node E.
Perfect Binary Tree
A perfect binary tree is a binary tree in which all the internal nodes have 2 children. Below is an example perfect binary tree.
TODO: Add other types, advantages, applications and some code.