6 Special Types of Binary Trees Explained To Kids

This post is also available in: हिन्दी (Hindi) العربية (Arabic)

In this article “6 Special Types of Binary Trees Explained To Kids”, we walk you through different types of binary trees in the data structure. Know about these different types of binary trees and answer the questions in a quiz at the end of the article. Let’s first understand what is a tree in data structure?

What is Tree in Data Structure?

There are many other data structures such as arrays, linked lists, stacks, and queues. All these data structures are linear data structures. Apart from linear data structures, there is one more type. It is a non-linear data structure.

A linear data structure stores data sequentially, whereas a non-linear data structure stores data non-linearly.

6 Special Types of Binary Trees Explained To Kids
Linear Data Structure
6 Special Types of Binary Trees Explained To Kids
Non Linear Data Structure

The advantage of non-linear over linear data structure is the time complexity in the case of linear data structure is more as compared to a non-linear data structure. That’s why non-linear data structures allow quicker and easier access to the data.

A tree is a non-linear hierarchical data structure that consists of nodes connected by edges.

6 Special Types of Binary Trees Explained To Kids
Tree in Data Structure

Tree Terminologies

Node is an entity that contains a key or a value and points to other nodes.

Edge is a link between two nodes.

Root is the topmost node of a tree.

The last nodes of each path are called leaf nodes or external nodes

The nodes that are not leaf nodes are called internal nodes.

The height of a node is the number of edges from the node to the deepest leaf (i.e., the longest path from the node to a leaf node).

The depth of a node is the number of edges from the root to the node.

Height of a tree is the height of the root node or the depth of the deepest node.

The degree of a node is the total number of branches of that node.

If A and B are two nodes, such that the height of node B is n and that of node A is (n – 1), then A is called the parent node of B, and B is called the child node of A.

Two nodes are called siblings if their depth is the same.

All nodes whose depths are greater than the depth of any given node X are called descendant nodes of node X.Similarly, all nodes whose depths are lesser than the depth of any given node X are called ancestor nodes of node X.

What is a  Binary Tree?

A binary tree is a tree data structure in which each parent node can have at most two child nodes(0, 1, or 2).

6 Special Types of Binary Trees Explained To Kids
Binary Tree

Types of Binary Trees

The following are the different types of binary trees:

  1. Full Binary Tree: A full binary tree is a special type of binary tree in which every node has either two or no children. We can also say that a full binary tree is a binary tree in which all nodes except leaf nodes have two children. (Leaf nodes are the external nodes and hence have no child node)
6 Special Types of Binary Trees Explained To Kids
Full Binary Tree

2. Complete Binary Tree: A binary tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible.

6 Special Types of Binary Trees Explained To Kids
Complete Binary Trees
6 Special Types of Binary Trees Explained To Kids
Not a Complete Binary Tree

3. Perfect Binary Tree: A binary tree is called a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level.

6 Special Types of Binary Trees Explained To Kids
Perfect Binary Tree

4. Balanced Binary Tree: A binary tree is called Balanced Binary Tree in which the difference between the left and the right subtree for each node is either 0 or 1.

6 Special Types of Binary Trees Explained To Kids
Balanced Binary Tree (df = (height of left child node) – (height of right child node))
6 Special Types of Binary Trees Explained To Kids
Unbalanced Binary Tree (df = (height of left child node) – (height of right child node))

5. Degenerate (or Pathological) Binary Tree: A binary tree where every internal node has only one child node. This type of binary tree is performance-wise the same as a linked list.

6 Special Types of Binary Trees Explained To Kids
Degenerate Binary Tree

6. Skewed Binary Tree: A binary tree where every internal node has only one child node. If all the internal nodes have a left child node, it is called Left Skewed Binary Tree and if all the internal nodes have a right child node, it is called Right Skewed Binary Tree.

6 Special Types of Binary Trees Explained To Kids
Left Skewed Binary Tree
6 Special Types of Binary Trees Explained To Kids
Right Skewed Binary Tree

Implementing Binary Tree in C++

A typical binary tree has the following components:

  • A left subtree
  • A root node
  • A right subtree

The following code is used to create a binary tree in C++:

struct node
{
  int key_value;
  node *left;
  node *right;
};

The root contains the key_value and it points to two other nodes – one on the left and the other on right.

6 Special Types of Binary Trees Explained To Kids

Use of Binary Trees

Unlike Array and Linked List, which are linear data structures, a tree is a hierarchical (or non-linear) data structure.

  • One reason to use trees might be because you want to store information that naturally forms a hierarchy. e.g., implementing a file system on a computer.
  • If we organize keys in form of a tree (with some ordering e.g., Binary Search Tree), we can search for a given key quicker as compared to linear data structures.

[tqb_quiz id=’2730′]

Leave a Comment