Introduction to Binary Tree

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.

  • 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-

    1. Every level must be completely filled

    2. All the leaf elements must lean towards the left.

    3. 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.