Types of Binary trees

Full or Strict Binary Tree 

Binary tree in which every node contains zero or two children nodes. In other words, the binary tree with all nodes having two children except leaf nodes.

Let’s visualize Full Binary Tree through examples

Complete Binary Tree

In this type of binary tree, all levels except the last level must be completely filled. In the last level, all nodes must be as left as possible.

Let’s visualize a Complete Binary Tree through examples

Perfect Binary Tree

A binary tree in which all internal nodes have two children and all leaf nodes are at the same level (i.e., last level).

Let’s visualize this type of Binary Tree through an example

So, all perfect binary trees are full as well as complete binary trees but not vice versa.

Also see, Perfect Binary Tree Specific Level Order Traversal

Degenerate Binary Tree

If each internal node has only one child node in a binary tree, it is called a Degenerate Binary tree.

Let’s visualize this type of binary tree through examples.

Balanced Binary Tree

If in a binary tree, the height of the left subtree and right subtree differ by at most 1, then it is a Balanced  Binary Tree.

AVL tree and Red-Black Tree come under the balanced binary tree.

Let’s visualize this type of binary tree through examples.

Check out this problem - Mirror A Binary Tree

Special Types of Trees

Special types of trees are unique data structures that provide specific functionalities and optimizations for different applications in computer science. Each type of tree serves a particular purpose, enhancing data organization and retrieval efficiency. Below are some significant special trees and their characteristics:

1. Binary Search Tree
2. AVL Tree
3. Red Black Tree
4. B Tree
5. B+ Tree
6. Segment Tree

Binary Search Tree

A Binary Search Tree (BST) is a binary tree where each node follows a specific order: the left child contains values less than its parent, and the right child holds values greater than its parent. This property enables efficient searching, inserting, and deleting operations, usually with a time complexity of O(log n) for balanced trees.

Example:

        15
      /  \
     10   20
    / \   / \
   8  12 17 25

In this BST, the left child of 15 is 10 (less than 15), and the right child is 20 (greater than 15). The same rule applies to all nodes.

AVL Tree

An AVL Tree is a self-balancing Binary Search Tree where the heights of the two child subtrees of any node differ by at most one. When this property is violated due to insertions or deletions, rotations are performed to maintain balance. This guarantees O(log n) time complexity for operations, ensuring efficient performance even in the worst case.

Example:

        30
       /  \
      20   40
     / \     \
    10  25    50

Here, the tree remains balanced after any insertions, ensuring efficient operations.

Red Black Tree

A Red-Black Tree is a type of self-balancing Binary Search Tree that maintains balance using an additional property of coloring nodes red or black. It ensures that no two red nodes are adjacent and that every path from the root to the leaves contains the same number of black nodes. This structure allows for O(log n) time complexity for search, insert, and delete operations, making it suitable for implementations that require frequent modifications.

Example:

        10 (B)
       /   \
      5 (R) 15 (R)
     / \      \
   2 (B) 7 (B) 20 (B)

In this example, red nodes cannot have red children, and the tree maintains balance through its coloring rules.

B Tree

A B Tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. Unlike binary trees, B Trees can have multiple children per node, which optimizes storage by minimizing the number of disk accesses in databases. This makes B Trees ideal for database and file systems where large blocks of data need to be managed efficiently.

Example:

          [10, 20]
         /    |    \
       [5]   [15]  [25, 30]

In this B Tree, each node can have multiple keys, and the tree remains balanced, minimizing disk access in databases.

B+ Tree

A B+ Tree is an extension of a B Tree that includes all values at the leaf nodes and maintains a linked list of these leaves for easy range queries. Non-leaf nodes only store keys for navigation, allowing for more efficient searching and insertion operations. This structure is commonly used in databases and filesystems, ensuring optimized performance for large datasets.

Example:

          [20, 40]
         /    |    \
       [10]  [30]  [50, 60]
                |
               [35] --> [45]

Here, all data values are at the leaf nodes, allowing efficient range queries by following the linked list of leaves.

Segment Tree

A Segment Tree is a binary tree used for storing intervals or segments. It allows querying the sum or minimum/maximum value in a segment efficiently. Each leaf node represents an element of the array, while internal nodes represent the aggregation of values from their children. This structure is particularly useful in scenarios that involve multiple range queries on arrays, providing O(log n) time complexity for updates and queries.

Example:

         [0, 5]
        /      \
      [0, 2]   [3, 5]
      /   \      /   \
   [0,1] [2]  [3,4] [5]

In this Segment Tree, each node represents a range of indices, and querying is efficient, providing results for sum or minimum over specified intervals.

Frequently Asked Questions

How many types of binary trees are there?

There are several types of binary trees, including full, complete, perfect, balanced, degenerate, and skewed binary trees, each with unique properties.

What are the different types of binary expression trees?

The main types of binary expression trees include postfix, prefix, and infix trees, which represent mathematical expressions in different notational forms.

What is another name for a strictly binary tree?

A strictly binary tree is also known as a full binary tree, where every node has either zero or two children.

What are the different types of traversals in Binary Trees?

There are mainly three types of traversal techniques in Binary Trees.
In order
Preorder
Postorder

What is a Perfect Binary Tree?

Binary tree in which all internal nodes have two children and all leaf nodes are at the same level (i.e., last level).

What is the need for balancing Binary Trees?

A balanced binary tree optimizes search time in the tree.
Search time complexity in a balanced binary tree is O(log n) in the worst case, but for an unbalanced tree, it is O(n), where n is the number of nodes. So maintaining a balanced tree is beneficial for large trees.

Conclusion

In this article, we have explored various types of binary trees and how they are different from each other.

Side by side, we should also learn about insertion, searching, and deletion operations in  Binary trees.

You can practice these concepts along with a wide range of coding questions commonly asked in interviews in Code360 Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here. 

Recommended Problems:

• Binary Tree vs Binary Search Tree
• Balanced Binary Tree
• Construct a Strict Binary Tree
• Construct a Complete Binary Tree
• Implementing Binary Tree in Java

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Code360

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Code360

Happy learning!