1. What is Binary Tree?
A binary tree is a tree-type non-linear data structure with a maximum of two children for each parent. Every node in a binary tree has a left and right reference along with the data element. The node at the top of the hierarchy of a tree is called the root node. The nodes that hold other sub-nodes are the parent nodes.
A parent node has two child nodes: the left child and the right child. Hashing, routing data for network traffic, data compression, preparing binary heaps, and binary search trees are some of the applications that use a binary tree.
2. Terminologies related to a Binary Tree
Node: A node is a basic unit of a data structure, such as a linked list or tree data structure. Nodes contain data and also may link to other nodes.
Root: A tree’s topmost node.
Parent: Each node (apart from the root) in a tree that has at least one sub-node of its own is called a parent node.
Child: A node that straightway came from a parent node when moving away from the root is the child node.
Leaf Node: These are external nodes. They are the nodes that have no children.
Internal Node: As the name suggests, these are inner nodes with at least one child.
Depth of a Tree: The depth of a node in a binary tree is the total number of edges from the root node to the target node. Similarly, the depth of a binary tree is the total number of edges from the root node to the most distant leaf node.
Height of a Tree: It is the number of edges from the node to the deepest leaf. The tree height is also considered the root height.
3. Types of Binary Tree
Full Binary Tree: A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children.
Complete Binary Tree: A complete binary tree is just like a full binary tree but with the following major differences-
Every level must be completely filled
All the leaf elements must lean towards the left.
The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.
- Perfect Binary Tree: A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level
Balanced Binary Tree: It is a type of binary tree in which the difference between the height of the left and the right subtree for each node is either 0 or 1.
Degenerate or Pathological Binary Tree: A degenerate or pathological tree is a tree having a single child either left or right. This means that the tree will behave like a linked list data structure.
Interesting Fact: The height of a Degenerate Binary Tree is equal to the total number of nodes in that tree.
Skewed Binary Tree: A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.
In the next blog, we'll discuss the basic operations of a binary tree.