Binary tree and its types in Data Structures

A binary tree is an abstract data type, non-primitive and non-linear data structure consisting of a finite set of nodes such as:

• It is either empty or
• It consists of a node called the root node with, at the most, two disjoint binary trees connected to it called the left subtree and the right subtree.

Properties of Binary Trees in Data Structures

Now, we will learn about some of the properties of Binary Trees –

1. The maximum number of nodes at the first level of the Binary Tree is 2^(n-1).
2. The maximum number of nodes in a Binary Tree of Height h is 2^h – 1.
3. In a Binary Tree with n nodes, the Minimum possible height is Floor(log₂(n+1))
4. In a binary tree, the Number of Leaf Nodes is always One more than the internal nodes with Two Children

Types of Binary Trees in Data Structures

Strictly Binary Tree in Data Structure

A binary Tree is called a strictly binary tree if every node has 0 or 2 children. Here, every non-leaf node in a binary tree has nonempty left and right subtrees. All of the nodes in a strictly binary tree are of degree zero or two, never degree one.

Given below is an example of a Strictly Binary Tree

Complete Binary Tree in Data Structure

A binary tree is known as a complete binary tree if it’s all its levels are completely filled except possibly the last level where all the nodes are stored as left as possible.

Given below is an example of a complete binary tree –

Perfect Binary Tree in Data Structure

It is a binary tree in which all internal nodes have two children and all the leaves are at the same level.

Given below is an example of a perfect binary tree –

Extended Binary Tree in Data Structure

An extended binary tree is a special form of a binary tree. A binary tree is an extended binary tree if it has strictly either zero or two children. Any binary tree can be promoted to an extended binary tree by inserting new nodes as children to the nodes with null values in their address fields. The new nodes can be represented by rectangles.

Try these Data Structures MCQ Tests