Do you think IIT Guwahati certified course can help you in your career?
Introduction
A binary tree is a hierarchical data structure composed of nodes, each containing a value and two child nodes (left and right). It efficiently organizes and searches data by following a specific order.
Binary trees are fundamental in computer science and are used in various applications such as search algorithms, expression parsing, and decision-making processes. They provide a foundation for more complex tree structures like AVL and red-black trees. In this article, we will discuss these in more detail.
M-ary Trees
M-ary tree is a rooted tree where every node has at most m children (i.e. <= m). A tree is a full m-ary tree if every internal node has m children.
What are Binary trees in Data Structure?
A Binary tree is an M-ary tree with m = 2.
Binary trees are a particular type of tree where each internal node have at most two children.
A Binary Tree can also be defined as a tree where each vertex has a degree of at most 2.
The root node divides the tree into two subtrees:-
Left sub-tree
Right sub-tree
In Example 1, the data 45, 5, 18, 35 and 16 form the left subtree and 64, 14 and 20 form the right sub-tree of root node 13.
In Example 2, data B form the left subtree and data C, D and E form the right subtree of root node A.
Any node N in a binary tree can have 0, 1 or 2 successors.
Properties of a binary tree
If ‘ l ’ is the level of a binary tree, the maximum number of nodes on any level in a binary tree is 2l.
For example, the root node is at level 0, so the number of nodes at the root is 20 = 1.
The children of the root node are at level 1, so the maximum number of nodes at level 1 is 21 = 2, and so on.
This can be proved by mathematical induction.
The maximum number of nodes possible in a tree of height h is 2h- 1
Here the root node is considered to be at the height of 1. ( In some books, the height of the root node is considered to be at the height of 0. Here, the formula is considered as 2h+1- 1.)
For example, the root node is at the height of 1. So 21- 1 = 1 node, which is true.
The children of the root node are at the height of 2. So 22- 1 = 3 nodes, which is true.
This can be proved by mathematical induction.
The minimum number of nodes in a binary tree of height h is ‘ h ‘.
For example, the root node is at level 1, so the minimum number of nodes at level 1 is 1.
Since the minimum number of nodes at the first level, there can be only one node whose height is 2. So the minimum number of nodes at the height of 2 is 2.
For a non-empty binary tree, if “n” is the number of edges and “e” is the number of edges, then n = e+1
In the above example, there are 15 nodes, so the number of edges e = 15+1=16 is valid.
Types of binary trees
Complete Binary Tree
A binary tree is a complete binary tree if, at all its levels except the last level, it has the maximum number of nodes, and nodes at the previous level appear as left as possible.
Key Property: Nodes are as far left as possible.
Use Case: It is commonly used in heap data structures (like a binary heap).
Example: A waiting queue where each row is filled from the front before starting the next.
Full Binary Tree
A binary tree is a full binary tree in which each node has either 0 or 2 children.
Key Property: No node has only one child.
Use Case: Used in expression trees and decision trees.
Example: A tournament bracket where every match has exactly two players.
Perfect Binary Tree
A binary tree is a perfect binary tree in which all the internal nodes have two children and all the leaf nodes are at the same level.
Key Property: All levels are fully filled.
Use Case: Useful in calculating the exact number of nodes.
Example: Like a pyramid where every level is completely filled with blocks.
Degenerate Tree
Binary Trees where every parent node has one child, and it can be either left or right.
Key Property: The tree has maximum height, reducing efficiency.
Use Case: Demonstrates worst-case performance in binary trees.
Example: Like a chain of command with only one person reporting to each superior.
Skewed trees
A binary tree where every parent node has only one child and that child should be strictly either left or right of every parent node.
Key Property: Can be left-skewed or right-skewed.
Use Case: Highlights inefficiency when trees aren't balanced.
Example: Like a falling domino line going only in one direction.
Balanced Binary Tree
A balanced binary tree is a tree where the height of the two subtrees of every node differ by no more than one.
Key Property: It maintains optimal time complexity for insert, delete, and search operations (O(log n)).
Use Case: Keeps data access efficient in dynamic datasets.
Example: Like a see-saw that stays level — if one side gets too heavy, it's adjusted.
Binary Search Tree (BST)
A Binary Search Tree is a binary tree where each node follows the order: left child < parent < right child.
Key Property: Enables efficient searching, insertion, and deletion.
Use Case: Used in databases and file systems for fast lookups.
Example: Like a dictionary, where words are sorted alphabetically for faster access.
AVL Tree
An AVL Tree is a self-balancing binary search tree where the difference in height between the left and right subtrees (balance factor) is at most 1.
Key Property: Guarantees O(log n) time complexity for all operations.
Use Case: Suitable for applications requiring frequent insertions and deletions.
Example: Like a tightrope walker adjusting each step to maintain perfect balance.
Red-Black Tree
A Red-Black Tree is a self-balancing binary search tree where each node is colored either red or black with certain properties to maintain balance.
Key Property: Ensures balanced height for worst-case efficiency.
Use Case: Used in Java’s TreeMap and C++ STL map/set implementations.
Example: Like traffic rules ensuring smooth and balanced traffic at intersections.
Threaded Binary Tree
A Threaded Binary Tree replaces NULL pointers with references (threads) to in-order predecessor or successor, optimizing traversal.
Key Property: Enables fast in-order traversal without using recursion or a stack.
Use Case: Used in memory-efficient tree traversal operations.
Example: Like adding shortcut links in a book index for quicker flipping.
Representation of binary tree
Array representation (Implicit Representation )
The array representation of a binary tree is a static representation. Here size of the array is declared beforehand, which is a massive disadvantage because if we declare an array of size 10, then after 10, no more elements can be added to the tree, even if we want to. Anyway, let us see how the elements of a tree are stored in an array.
Consider a tree shown below:-
Here the numbers on top of each node represent their respective positions in the array. When these elements of the tree are arranged in an array, the height of it will look like:-
For any node with index i, 1< i <= n
Left Child ( i ) = 2*i + 1
Right Child( i ) = 2*i + 2
Binary trees were created for efficient insertion, deletion and traversal operations, but implementing binary trees with an array is quite costly, so we have another representation of tree called the linked representation of binary tree ( Note:- This is not Linked list, as the Linked list is a linear Data Structure )
Linked Representation ( Explicit Representation )
This linked representation is the most efficient representation of the binary tree. For the linked representation of a binary tree, we use the concept of a Doubly Linked List.
In the above figure, a node with data 10 is represented in linked representation. Here LC represents the address of the left child, and RC represents the address of the right child, respectively.
So, the structure of a node in linked representation is as follows:-
So a binary tree representation using linked representation is as follows:-
In the linked representation of binary trees, we create a node whenever it is necessary. It is like the dynamic insertion of a node, whereas in an array, it is static, so a linked list representation of binary trees is advantageous.
Below is a snippet for creating a node in the C language.
Applications of Binary Trees
1. General Applications
DOM Representation in HTML: The Document Object Model is structured as a tree, where elements are nested within each other, forming parent-child relationships.
File Explorers: Operating systems represent directories and files using a tree-based structure for efficient traversal and organization.
Expression Evaluation: Binary Expression Trees are used to evaluate mathematical expressions by arranging operators and operands hierarchically.
Syntax Parsing in Compilers: Compilers use binary trees to parse and analyze syntax structures for efficient code translation.
2. Hierarchical Data Representation
File Systems: Binary trees help represent hierarchical folder structures in storage systems.
Organizational Charts: Binary trees can model employee-supervisor relationships in a top-down manner.
XML/HTML Parsing: Tree structures parse markup languages effectively, ensuring tags are opened and closed in a proper sequence.
Taxonomies: Trees are often used in biology and databases to represent classification hierarchies.
3. Applications of Binary Search Trees (BSTs)
Efficient Searching: BSTs provide logarithmic time complexity for search operations in sorted data.
Auto-complete and Suggestions: BSTs assist in providing quick lookups in text editors or search engines.
Dictionaries and Maps: Used internally to implement key-value pair structures in programming libraries.
Data Retrieval Systems: In databases, BSTs support fast data retrieval using range queries.
4. Applications of Binary Heap Trees & Decision Trees
Priority Queues: Binary heaps help implement priority queues for job scheduling or process management.
Graph Algorithms: Heaps are used in Dijkstra’s shortest path and Prim’s algorithm for efficient graph traversal.
Decision Trees in ML: Used for classification and regression problems in supervised learning.
Structured Organization: They maintain a clear parent-child hierarchy ideal for representing nested data.
Efficient Searching & Sorting: BSTs allow O(log n) time complexity for many operations, improving performance.
Balanced Storage: AVL and Red-Black Trees prevent skewness, ensuring optimal performance even after many insertions.
Recursive Processing: Binary trees naturally support recursive algorithms due to their structure.
Flexible Data Types: Binary trees can handle strings, integers, and complex objects uniformly.
Scalability: They can grow dynamically with minimal restructuring compared to arrays or lists.
Disadvantages of Binary Trees
Skewed Tree Issues: In the worst cases, binary trees can become skewed and degrade to linear performance (O(n)).
Pointer Overhead: Each node requires additional memory to store left and right child pointers.
Complex Balancing: Self-balancing trees like AVL or Red-Black trees involve intricate logic to maintain balance.
Two-Child Limitation: Binary trees only allow two children per node, limiting representation for wider hierarchies.
Frequently Asked Questions What are the different types of Binary Trees?
Different types of binary trees are:- Complete Binary Tree Full Binary Tree Skewed Binary Tree Perfect Binary Tree Degenerate Binary Trees
What is the advantage of using a binary tree?
The advantages are it helps in the storage of data in a hierarchical manner which helps in easy traversal operation, and it makes insertion and deletion faster than the arrays.
What are the time and space complexities of using binary trees?
The time and space complexities of a binary tree are O( n ).
Where are the uses of binary trees?
The primary use of binary trees is to search and sort as the data is stored hierarchically.
Conclusion
So to summarise all you read, it covers topics about m-ary trees. We have looked at what a binary tree is, then the different properties of a binary tree, and how a binary tree is represented using arrays and linked lists. Further, we have seen why using an array for a binary tree is inefficient and how linked representation of a binary tree helps in overcoming the difficulties faced by the array.
240+ registered 
