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
 Every level must be completely filled
 All the leaf elements must lean towards the left.
 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: leftskewed binary tree and rightskewed 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
 All nodes in the left subtree are less than the root node
 All nodes in the right subtree are greater than the root node
 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
Operation  Best Case Complexity  Average Case Complexity  Worst Case Complexity 

Search  O(log n)  O(log n)  O(n) 
Insertion  O(log n)  O(log n)  O(n) 
Deletion  O(log n)  O(log n)  O(n) 
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. Inorder 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 inorder traversal of the Binary Search Tree gives us the ascending order of values stored in the tree.
2. Preorder Traversal
In preorder 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. Postorder Traversal
In postorder 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 inorder, postorder, preorder 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
 Every level must be completely filled

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.