Binary Tree

In a normal tree, every node can have any number of children. A binary tree is a special type of tree data structure in which every node can have a maximum of 2 children. One is known as a left child and the other is known as right child.

A tree in which every node can have a maximum of two children is called Binary Tree.

In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than 2 children.

Example

There are different types of binary trees and they are…

Types of Binary Trees-

Binary trees can be of the following types-

  1. Rooted Binary Tree
  2. Full / Strictly Binary Tree
  3. Complete / Perfect Binary Tree
  4. Almost Complete Binary Tree
  5. Skewed Binary Tree

1. Rooted Binary Tree-

A rooted binary tree is a binary tree that satisfies the following 2 properties-

  • It has a root node.
  • Each node has at most 2 children.

Example-

2. Full / Strictly Binary Tree-

  • A binary tree in which every node has either 0 or 2 children is called as a Full binary tree.
  • Full binary tree is also called as Strictly binary tree.

Example-

Here,

  • First binary tree is not a full binary tree.
  • This is because node C has only 1 child.

3. Complete / Perfect Binary Tree-

A complete binary tree is a binary tree that satisfies the following 2 properties-

  • Every internal node has exactly 2 children.
  • All the leaf nodes are at the same level.
  • Complete binary tree is also called as Perfect binary tree.

Example-

Here,

  • First binary tree is not a complete binary tree.
  • This is because all the leaf nodes are not at the same level.

4. Skewed Binary Tree-

A skewed binary tree is a binary tree that satisfies the following 2 properties-

  • All the nodes except one node has one and only one child.
  • The remaining node has no child.

OR

A skewed binary tree is a binary tree of n nodes such that its depth is (n-1).

Example-

Ezoic