Types of Binary Trees in C

Binary trees can be of many types depending on the parameter we took for the classification of the trees. The following are the types of binary trees:

According to Number of Children

• Full Binary Tree: A binary tree in which every node other than the leaves has two children.
• Degenerate Binary Tree: A tree where each parent node has only one child.
• Skewed Binary Trees: A binary tree in which all the nodes are skewed to the left or right.

According to Completion of Levels

• Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, and the last level has all keys as left as possible.
• Perfect Binary Tree: A binary tree in which all the internal nodes have two children and all leaves are at the same level.
• Balanced Binary Tree: A binary tree in which the height of the left and right subtrees of any node differ by not more than one.

According to Node Values

• Binary Search Tree (BST): A binary tree in which all the left descendants of a node are less than the node and all the right descendants are greater than the node.
• AVL Tree: A self-balancing binary search tree where the difference in heights between left and right subtrees is at most one.
• Red-Black Tree: A binary search tree with an extra bit of storage per node: its color, which can be either red or black. It ensures the tree remains balanced.
• B Tree: A self-balancing search tree in which nodes can have multiple children and is optimized for systems that read and write large blocks of data.
• B+ Tree: An extension of the B tree which maintains the data in a sorted order and allows sequential access.
• Segment Tree: A binary tree used for storing the intervals or segments. It allows querying which of the stored segments contain a given point.
• Fenwick Tree (Binary Indexed Tree): A data structure that provides efficient methods for calculation and manipulation of the prefix sums of a table of values.

A binary tree is a non-linear hierarchical data structure in which each node has at most two children known as the left child and the right child. It can be visualized as a hierarchical structure where the topmost node is called the root node and the nodes at the bottom are called leaf nodes or leaves.

In this article, we will learn the basics of binary trees, types of binary trees, basic operations that can be performed on binary trees as well as applications, advantages, and disadvantages of binary trees in C.