Introduction to Binary Tree - Learn DSA


Things to be discussed in this Article

  • Introduction

  • Binary Tree

    • Types of Binary Tree

    • Traversals in a Binary Tree

    • Applications

  • Implementation (Next Article)

  • Practice Problems (Next Article)


Introduction

When starting programming, it is common and may be easier to learn about linear data structures like an array, queue, stack, etc. To perform any operation in a linear data structure, the time complexity increases with the increase in the data size. In today's computational world, that becomes a little difficult.

Trees are well known as non-linear data structures. That is, they don't store the data linearly, they organize the data hierarchically. Something like this,


In the above picture, each box is usually called a node. The advantage of this is. it allows us a quicker and easier way to access our data. There are many types of trees with different use cases. Some of them are,

  • Binary Tree

  • Binary Search Tree

  • AVL Tree

  • B-Tree and so on...

We'll first look into what a Binary Tree is and how it works.


Binary Tree

It is a special type of tree data structure wherein each node has at most two nodes as it's children which are referred to as the left child and the right child. It looks like this,


Types of Binary Tree

  • Full Binary Tree

A full binary tree is a special type of binary tree in which every parent node/internal node has either two or no children. It is also known as the proper binary tree.


  • Perfect Binary Tree

A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.


  • Complete Binary Tree

A complete binary tree is just like a full binary tree but with two major differences,

  1. Every level must be filled.

  2. All the leaf elements must lean towards the left.

  3. The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.


  • Degenerate or Pathological Tree

A degenerate or pathological tree is the tree having a single child either left or right.


  • Skewed Binary Tree

A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.


  • Balanced Binary Tree

It is a type of binary tree in which the difference between the left and the right subtree for each node is either 0 or 1.



Traversals in a Binary Tree

  • Preorder

  1. Print the value of the node.

  2. Go to the left child and print it. This is iff it has a left child.

  3. Go to the right child and print it. This is iff it has a right child.


  • Inorder
  1. Go to the left child and print it. This is iff it has a left child.

  2. Print the value of the node.

  3. Go to the right child and print it. This is iff it has a right child.


  • Postorder
  1. Go to the left child and print it. This is iff it has a left child.

  2. Go to the right child and print it. This is iff it has a right child.

  3. Print the value of the node.


Note: There are other types of traversals such as level order traversal, vertical order traversal, etc.

Applications

  • For easy and quick access to data.

  • In router algorithms.

  • To implement a heap data structure.

  • Syntax tree.


Conclusion

In this article, we learnt about a new tree data structure called a binary tree. We also saw how it used, the types of binary trees, how we traverse a binary tree and where binary trees are useful and are applied. In the next article, we'll see how to implement a binary tree and some sample problems for your practice will be given.


The Related Articles which you should read after this

If there is any error or you have any doubt in the article then do ask us through the comment section, we will be happy to help you.

If you think that this article has helped you to learn something then do share this with your friends.

Thank You for Reading.