What is Binary Tree in Data Structure?

Last Updated on January 13, 2023 by Prepbytes

In this article, we will discuss binary tree in data structure. This is one of the most important topics of data structure.

Binary Tree in Data Structure

A binary tree is a tree data structure in which each parent node can have at most two children. Each node of a binary tree consists of three items:

• data element
• address of left child
• address of right child

Structure of Node

structure node
{
int data;
structure node *left;
structure node *right;
};

Types of Binary Tree

1. 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.

2. 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.

3. Complete Binary Tree

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

1. Every level must be completely 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.

5. 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.

6. Balanced Binary Tree

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

Binary search tree in data structure

A node in a binary tree is represented by a structure containing data and two pointers to other structures of the same type. It is a type of binary tree because each tree node has at most two children. It is called a search tree because it can be used to search for the existence of a number in O(log(n)) time.

The properties that separate binary search trees from regular binary trees are

1. All nodes in the left subtree are less than the root node
2. All nodes in the right subtree are greater than the root node
3. Both subtrees of each node are also BST.

Algorithm of Search Operation

The algorithm relies on the property of BST where all left subtrees have values ​​below the root and all right subtrees have values ​​above the root.
If the value is less than the root, we can say for sure that the value is not in the right subtree; we need to only search in the left subtree and if the value is above the root, we can say for sure that the value is not in the left subtree; we need to only search in the right subtree.

Binary Search Tree Complexities

Time Complexity

Here, n is the number of nodes in the tree.

Space Complexity: The space complexity for all the operations is O(n).

Binary tree traversal in data structure

What is the Traversal of a Binary Tree?

A binary tree is a data structure in which data is stored in a hierarchical form. Traversal of the binary tree means visiting every node of the tree. The process of accessing the nodes of a tree in some order is called a traversal of a binary tree. Any process for visiting all of the nodes is called a traversal.

What is Traversal Order?

Unlike linear data structures(Array, Queues, Linked List, Queues, etc.) that have only one way to traverse them but the tree data structure can be traversed in multiple ways.
The tree can be traversed in three ways:

1. In-order Traversal
In inorder traversal of the binary tree, these 3 steps are recursively performed.

Step 1: Firstly left subtree is visited
Step 2: Then the root is visited
Step 3: Then the right subtree is visited.

An in-order traversal of the Binary Search Tree gives us the ascending order of values stored in the tree.

2. Pre-order Traversal
In pre-order traversal of a binary tree, these 3 steps are recursively performed.

Step 1: Firstly root is visited
Step 2: Then the left subtree is visited
Step 3: Then finally the right subtree is visited.

3. Post-order Traversal
In post-order traversal of the binary tree root node is visited at the last. In this traversal, these 3 steps are recursively performed.

Step 1: Firstly left subtree is visited
Step 2: Then the right subtree is visited.
Step 3: And at last, the root is visited.

What are Tree Traversal Methods?

Traversal Implementation in C++

// C++ program to display in-order, post-order, pre-order traversal of tree
#include <iostream>
using namespace std;

/* A binary tree node has data stored as value, pointer to left child
and right child */
struct Node {
  int value;
  struct Node *left, *right;
};

//function for creating new tree node
Node* createNode(int value){
  Node* t = new Node;
  t->value = value;
  t->left = t->right = NULL;
  return t;
}

/* printing postorder traversal of binary tree */
void postorder(struct Node* root){
  if (root == NULL)
    return;

  // first traverse left subtree
  postorder(root->left);

  // then traverse right subtree
  postorder(root->right);

  // now visit root node
  cout << root->value << " ";
}

/* inorder traversal of the binary tree*/
void inorder(struct Node* root){
  if (root == NULL)
    return;

  /* first visit left child */
  inorder(root->left);

  /* print root data */
  cout << root->value << " ";

  /* at last recur over right subtree */
  inorder(root->right);
}

/* Preorder traversal of the binary tree*/
void preorder(struct Node * root){
  if (root == NULL)
    return;

  /* display node value */
  cout << root->value << " ";

  /* then traverse left subtree */
  preorder(root->left);

  /* now traverse right subtree */
  preorder(root->right);
}
int main(){
  struct Node* n = createNode(1);
  n->left = createNode(2);
  n->right = createNode(3);
  n->left->left = createNode(4);
  n->left->right = createNode(5);

  cout << "\nPreorder traversal of  tree: \n";
  preorder(n);

  cout << "\nInorder traversal of tree: \n";
  inorder(n);

  cout << "\nPostorder traversal of tree: \n";
  postorder(n);

  return 0;
}

Output

Preorder traversal of binary tree:
1 2 4 5 3 
Inorder traversal of binary tree:
4 2 5 1 3 
Postorder traversal of binary tree:
4 5 2 3 1

Complete Binary Tree in Data Structure

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

1. Every level must be completely filled

2. All the leaf elements must lean towards the left, In other words, every node is filled in the direction of left to right.

                       5                                          7
                      / \                                        /  \
                   4     2                                    8     1
                  /\                                          /\    /
               11  9                                      6  4  5
   
            NOT C.B.T                               C.B.T

C.B.T stands for Complete Binary Tree

Threaded binary tree in data structure

Inorder traversal of the binary tree can either be done using recursion or with the use of an auxiliary stack. The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion. A binary tree is made threaded by making all right child pointers that would normally be NULL point to the inorder successor of the node (if it exists).
There are two types of threaded binary trees.

Single Threaded: Where a NULL right pointers is made to point to the inorder successor (if successor exists)

Double Threaded: Where both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively. The predecessor threads are useful for reverse inorder traversal and postorder traversal.

The threads are also useful for fast accessing ancestors of a node.

Conclusion
In this article, we have discussed what is binary search tree in data structure, binary tree traversal and its types, and complete binary tree in data structure.