Binary Tree Data Structure

A Binary Tree Data Structure is a hierarchical data structure in which each

node has at most two children, referred to as the left child and the right child.
It is commonly used in computer science for efficient storage and retrieval of
data, with various operations such as insertion, deletion, and traversal.

Binary Tree Traversals:

Tree Traversal algorithms can be classified broadly into two categories:
 Depth-First Search (DFS) Algorithms
 Breadth-First Search (BFS) Algorithms

Tree Traversal using Depth-First Search (DFS) algorithm can be further

classified into three categories:

 Preorder Traversal (current-left-right): Visit the current node before

visiting any nodes inside the left or right subtrees. Here, the traversal is root
– left child – right child. It means that the root node is traversed first then its
left child and finally the right child.
 Inorder Traversal (left-current-right): Visit the current node after visiting all
nodes inside the left subtree but before visiting any node within the right
subtree. Here, the traversal is left child – root – right child. It means that the
left child is traversed first then its root node and finally the right child.
 Postorder Traversal (left-right-current): Visit the current node after visiting
all the nodes of the left and right subtrees. Here, the traversal is left child –
right child – root. It means that the left child has traversed first then the right
child and finally its root node.

Tree Traversal using Breadth-First Search (BFS) algorithm can be further

classified into one category:

 Level Order Traversal: Visit nodes level-by-level and left-to-right fashion at

the same level. Here, the traversal is level-wise. It means that the most left
child has traversed first and then the other children of the same level from
left to right have traversed.

Let us traverse the following tree with all four traversal methods:

Binary Tree

Pre-order Traversal of the above tree: 1-2-4-5-3-6-7

In-order Traversal of the above tree: 4-2-5-1-6-3-7
Post-order Traversal of the above tree: 4-5-2-6-7-3-1
Level-order Traversal of the above tree: 1-2-3-4-5-6-7
 Auxiliary Operations On Binary Tree:
 Finding the height of the tree
 Find the level of the tree
 Finding the size of the entire tree.
Applications of Binary Tree:
 In compilers, Expression Trees are used which is an application of binary
trees.
 Huffman coding trees are used in data compression algorithms.
 Priority Queue is another application of binary tree that is used for searching
maximum or minimum in O(1) time complexity.
 Represent hierarchical data.
 Used in editing software like Microsoft Excel and spreadsheets.
 Useful for indexing segmented at the database is useful in storing cache in
the system,
 Syntax trees are used for most famous compilers for programming like GCC,
and AOCL to perform arithmetic operations.
 For implementing priority queues.
 Used to find elements in less time (binary search tree)
 Used to enable fast memory allocation in computers.
 Used to perform encoding and decoding operations.
 Binary trees can be used to organize and retrieve information from large
datasets, such as in inverted index and k-d trees.
 Binary trees can be used to represent the decision-making process of
computer-controlled characters in games, such as in decision trees.
 Binary trees can be used to implement searching algorithms, such as in
binary search trees which can be used to quickly find an element in a sorted
list.
 Binary trees can be used to implement sorting algorithms, such as in heap
sort which uses a binary heap to sort elements efficiently.

Types of Binary Tree





We have discussed Introduction to Binary Tree in set 1 and the Properties of Binary
Tree in Set 2. In this post, common types of Binary Trees are discussed.
Types of Binary Tree based on the number of children:
Following are the types of Binary Tree based on the number of children:
1. Full Binary Tree
2. Degenerate Binary Tree
3. Skewed Binary Trees
1. Full Binary Tree
A Binary Tree is a full binary tree if every node has 0 or 2 children. The
following are examples of a full binary tree. We can also say a full binary tree is
a binary tree in which all nodes except leaf nodes have two children.
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 a proper
binary tree.

Full Binary Tree

2. Degenerate (or pathological) tree

A Tree where every internal node has one child. Such trees are performance-
wise same as linked list. A degenerate or pathological tree is a tree having a
single child either left or right.
 Degenerate (or pathological) tree

3. 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.
 Skewed Binary Tree

Refer to this article to read about more on Skewed Binary Tree

Types of Binary Tree On the basis of the completion of levels:
1. Complete Binary Tree
2. Perfect Binary Tree
3. Balanced Binary Tree
1. 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.
A complete binary tree is just like a full binary tree, but with two major
differences:
 Every level except the last 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.
 Complete Binary Tree

Refer to this article to read about more on Complete Tree

2. Perfect Binary Tree
A Binary tree is a Perfect Binary Tree in which all the internal nodes have two
children and all leaf nodes are at the same level.
The following are examples of Perfect Binary Trees.
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.
 Perfect Binary Tree

In a Perfect Binary Tree, the number of leaf nodes is the number of internal
nodes plus 1
L = I + 1 Where L = Number of leaf nodes, I = Number of internal nodes.
A Perfect Binary Tree of height h (where the height of the binary tree is the
number of edges in the longest path from the root node to any leaf node in the
tree, height of root node is 0) has 2 h+1 – 1 node.
An example of a Perfect binary tree is ancestors in the family. Keep a person at
root, parents as children, parents of parents as their children.
Refer to this article to read about more on Perfect Tree
3. Balanced Binary Tree
A binary tree is balanced if the height of the tree is O(Log n) where n is the
number of nodes. For Example, the AVL tree maintains O(Log n) height by
making sure that the difference between the heights of the left and right
subtrees is at most 1. Red-Black trees maintain O(Log n) height by making sure
that the number of Black nodes on every root to leaf paths is the same and that
there are no adjacent red nodes. Balanced Binary Search trees are
performance-wise good as they provide O(log n) time for search, insert and
delete.
 Example of Balanced and Unbalanced 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. In the figure above, the root
node having a value 0 is unbalanced with a depth of 2 units.
Some Special Types of Trees:
On the basis of node values, the Binary Tree can be classified into the
following special types:
1. Binary Search Tree
2. AVL Tree
3. Red Black Tree
4. B Tree
5. B+ Tree
6. Segment Tree
Below Image Shows Important Special cases of binary Trees:
 Binary Tree Special cases

1. Binary Search Tree

Binary Search Tree is a node-based binary tree data structure that has the
following properties:
 The left subtree of a node contains only nodes with keys lesser than the
node’s key.
 The right subtree of a node contains only nodes with keys greater than the
node’s key.
 The left and right subtree each must also be a binary search tree.
 Algorithm To Construct Binary Tree Using Linked List
1. Base Case – If the head is NULL, then make the root NULL.
2. Create a queue.
3. Enqueue the first node of the linked list, and make it the root.
4. Traverse through the list, and do the following.
5. Dequeue a node from the queue. ...
6. Continue this till the end of the linked list.

Suppose the given linked list is 10 -> 12 -> 13 -> 23 -> 30 -> 36. For each
ith node, its children are the (2i+1)th and (2i+2)nd nodes of the list. So, the
children of 10 are 12 and 13. The children of 12 are 23 and 30. The children of
13 are 36 and NULL. All other child nodes are NULL. Hence, the complete
binary tree is :-

Application of Binary Trees:

 Search algorithms: Binary search algorithms use the structure of binary
trees to efficiently search for a specific element. The search can be
 performed in O(log n) time complexity, where n is the number of nodes in the
tree.
 Sorting algorithms: Binary trees can be used to implement efficient sorting
algorithms, such as binary search tree sort and heap sort.
 Database systems: Binary trees can be used to store data in a database
system, with each node representing a record. This allows for efficient
search operations and enables the database system to handle large
amounts of data.
 File systems: Binary trees can be used to implement file systems, where
each node represents a directory or file. This allows for efficient navigation
and searching of the file system.
 Compression algorithms: Binary trees can be used to implement Huffman
coding, a compression algorithm that assigns variable-length codes to
characters based on their frequency of occurrence in the input data.
 Decision trees: Binary trees can be used to implement decision trees, a
type of machine learning algorithm used for classification and regression
analysis.
 Game AI: Binary trees can be used to implement game AI, where each node
represents a possible move in the game. The AI algorithm can search the
tree to find the best possible move.

Advantages of Binary Tree:

 Efficient searching: Binary trees are particularly efficient when searching
for a specific element, as each node has at most two child nodes, allowing
for binary search algorithms to be used. This means that search operations
can be performed in O(log n) time complexity.
 Ordered traversal: The structure of binary trees enables them to be
traversed in a specific order, such as in-order, pre-order, and post-order.
This allows for operations to be performed on the nodes in a specific order,
such as printing the nodes in sorted order.
 Memory efficient: Compared to other tree structures, binary trees are
relatively memory-efficient because they only require two child pointers per
node. This means that they can be used to store large amounts of data in
memory while still maintaining efficient search operations.
 Fast insertion and deletion: Binary trees can be used to perform insertions
and deletions in O(log n) time complexity. This makes them a good choice
for applications that require dynamic data structures, such as database
systems.
 Easy to implement: Binary trees are relatively easy to implement and
understand, making them a popular choice for a wide range of applications.
 Useful for sorting: Binary trees can be used to implement efficient sorting
algorithms, such as heap sort and binary search tree sort.
Disadvantages of Binary Tree:
 Limited structure: Binary trees are limited to two child nodes per node,
which can limit their usefulness in certain applications. For example, if a tree
requires more than two child nodes per node, a different tree structure may
be more suitable.
 Unbalanced trees: Unbalanced binary trees, where one subtree is
significantly larger than the other, can lead to inefficient search operations.
This can occur if the tree is not properly balanced or if data is inserted in a
non-random order.
 Space inefficiency: Binary trees can be space inefficient when compared to
other data structures. This is because each node requires two child pointers,
which can be a significant amount of memory overhead for large trees.
 Slow performance in worst-case scenarios: In the worst-case scenario, a
binary tree can become degenerate, meaning that each node has only one
child. In this case, search operations can degrade to O(n) time complexity,
where n is the number of nodes in the tree.
 Complex balancing algorithms: To ensure that binary trees remain
balanced, various balancing algorithms can be used, such as AVL trees and
red-black trees. These algorithms can be complex to implement and require
additional overhead, making them less suitable for some applications.