Binary Tree in Data Structure

Among the core data structures in computer science, the binary tree stands out for its hierarchical organization, where each node connects to up to two child nodes. It forms the base of many algorithms and is widely used in applications such as searching, sorting, expression evaluation, and hierarchical data storage. So, whether you are preparing for coding interviews or developing efficient software applications, understanding a binary tree is important. In this article, we will discuss what a binary tree is, its terminologies, properties, types, operations, implementations, time and space complexity, advantages, disadvantages, and applications.

Table of Contents:

• What is Binary Tree in Data Structure?
• Terminology in Binary Tree in Data Structure
• Properties of Binary Tree in Data Structure
• Types of Binary Trees in Data Structure
• Binary Tree Traversal
• Binary Tree Operations
• Implementation of Binary Tree in Data Structure
• Binary Tree Time and Space Complexity Analysis
• Advantages of Binary Tree
• Disadvantages of Binary Tree
• Applications of Binary Tree
• Conclusion

What is Binary Tree in Data Structure?

A binary tree is a hierarchical data structure in which each node has at most two children, which are referred to as the left child and the right child. A binary tree organizes data in a tree-like structure with a root node at the top. 

In a tree, the top-most node is known as the root node, and nodes with no children are known as leaf nodes. In a binary tree, each node contains a data value, a reference to a left child, and a reference to a right child. If a node does not have a left or right child, then the corresponding pointer is set to null.

Example of a Binary Tree:

Here, 

• 10 is the root node.
• 5 and 20 are children of 10.
• 3 and 7 are children of 5.
• 30 is the right child of 20.
• Also, 3, 7, and 30 are leaf nodes.

Terminology in Binary Tree in Data Structure

Here are a few terms that are used in a binary tree in data structures:

1. Node: The basic building block of a binary tree is a node. Each node contains a data value, a left child pointer, and a right child pointer.
2. Root: The topmost node of the binary tree is called the root node. The root is the ancestor of all other nodes.
3. Parent: A node, except the root, that has one or more children is known as a parent node.
4. Child: A node that is directly connected below another node is called a child.
5. Leaf: A node without any children is a leaf node, which means it has no left or right child pointers.
6. Internal Node: A node with at least one child node is called an internal node.
7. Sibling: The nodes that share the same parent node are called siblings.
8. Subtree: A tree formed by any node and all of its descendants is known as a subtree. Every node defines the root of a subtree.
9. Level: It is the distance from the root counted by edges. The root node is at level 0, and the root’s children are at level 1.
10. Height of a Node: The longest path from the node to any leaf node below it is the height of a node.
11. Depth of a Binary Tree: The number of nodes on the longest path from the root node down to the deepest leaf node is the depth of a binary tree.
12. Depth of a Node: The distance from the root to that particular node is known as the depth of that node.
13. Height of a Binary Tree: The height of a binary tree is equal to the maximum depth of any node from the root node in the tree.
14. Degree of a Node: The Degree of a node is the number of children the node has. In a binary tree, the degree can be 0, 1, or 2.

Example:

Properties of a Binary Tree in Data Structure

Here are a few properties of binary trees in data structures that you must follow while solving any problem related to binary trees.

1. The maximum number of nodes at the level l of a binary tree is 2^l, in which the root is considered at level 0.
2. The maximum number of nodes in a binary tree of height h is (2^(h+1))-1 if the binary tree is a complete binary tree.
3. In a binary tree with n nodes, the minimum height is (log2(n+1))-1.
4. The maximum number of leaf nodes in a binary tree of height h is 2^h (a perfect binary tree will have this number of leaf nodes).
5. In a full binary tree, there is a relationship between the number of leaf nodes L and the number of internal nodes I, that is, L = I + 1.

Types of Binary Trees in Data Structure

Here are the 5 types of binary trees in data structure that are discussed briefly with examples.

1. Full Binary Tree

A full binary tree is a type of binary tree in data structure in which every node has either 0 or 2 children. In other words, we can say that no node in a full binary tree has only one child. This property of the full binary tree makes sure that every internal node has exactly two children, and leaf nodes do not have any children.

Key Properties of a Full Binary Tree:

• In a full binary tree, every level can have nodes, but each node has either 0 or 2 children.
• The number of leaf nodes L is L = I + 1 if the tree contains I internal nodes having children. 
• The total number of nodes N in a full binary tree is equal to 2L – 1.
• In a full binary tree with a total number of nodes n, the number of internal nodes (nodes with at least one child) is given by I = (n-1) / 2.
• In a full binary tree with a total number of nodes n, the number of leaf nodes is given by L = (n+1) / 2.

Example of a Full Binary Tree:    

Here, 

• Nodes 0 and 1 each have exactly two children.
• Nodes 2, 3, and 4 are leaf nodes with no children.

2. Perfect Binary Tree

A perfect binary tree is a special type of binary tree in data structure in which every internal node has exactly two children, and all leaf nodes are at the same level. This means that the tree is completely filled, with no missing nodes, making it perfectly balanced and symmetric.

Key Properties of a Perfect Binary Tree:

• A perfect binary tree of height h has exactly [2^(h+1)]-1 total nodes.
• The number of leaf nodes L in a perfect binary tree of height h is 2^h.
• The number of internal nodes I in a perfect binary tree is 2^h-1.
• The maximum number of nodes at any level is 2^i, and in a perfect tree, each level has exactly 2^i nodes.
• A perfect binary tree is both full and complete, but being complete or full alone does not imply perfection.

Example of a Perfect Binary Tree:

Perfect binary tree of height 2:

Here,

• Height (h) is 2 (root-to-leaf path with 2 edges).
• Total nodes: [2^(2+1)]-1=7.
• Leaf nodes: 2^2=4 (nodes 4, 5, 6, 7).
• All leaves (4,5,6,7) are at the same level (level 2).

3. Complete Binary Tree

A complete binary tree is a type of binary tree in data structure in which all levels are completely filled except the last level, which is filled from left to right without any gaps. It means that every level above the last must be full, and the last level can be incomplete. This property makes the complete binary trees useful for implementing efficient array-based data structures like binary heaps.

Key Properties of a Complete Binary Tree:

• If a complete binary tree has n nodes, the height h is approximately log2​n.
• The last level may not be fully filled, but all nodes at the last level must be packed to the left.
• A complete binary tree is not required to be perfect; only the perfect binary trees are both complete and have their last level fully filled.
• In an array representation of a complete binary tree,
• The root is at index 0,
• For a node at index i, the left child is at index 2i + 1, the right child is at index 2i + 2, and the parent index is (i – 1) / 2.
• Complete binary trees minimize the height for a given number of nodes, ensuring good performance in operations like insertion or deletion in heaps.

Example of a Complete Binary Tree:

A fully filled, complete tree (which is also perfect)

4. Degenerate Binary Tree

A degenerate binary tree is a type of binary tree in data structure in which each parent node has only one child. Due to this, the tree becomes a linked list, which means it grows linearly rather than branching out. It is also called a pathological binary tree. 

Key Properties of a Degenerate Binary Tree:

• Every node has either 0 or 1 child.
• The height of the tree becomes equal to the number of nodes minus one (i.e., h=n-1), which is the worst-case scenario for a binary tree.
• Operations like search, insert, and delete have O(n) time complexity same as a linked list.
• Degenerate trees show why balancing techniques (e.g., AVL trees, Red-Black trees) are needed for efficient binary search trees (BSTs).

Types of Degenerate Binary Trees:

There are two types of degenerated binary trees.

1. Left-Skewed Degenerate Binary Tree

It is a degenerate binary tree in which each node has only a left child, creating a straight path down the left. A left-skewed tree leans entirely to the left.

2. Right-Skewed Degenerate Binary Tree

It is a right-skewed degenerate binary tree in which each node has only a right child, creating a straight path down the right. A right-skewed tree leans entirely to the right.

Examples of Degenerate Binary Tree:

Here are the examples, and in both examples, every node has only one child, creating a straight path.

5. Balanced Binary Tree

A balanced binary tree is a type of binary tree in data structure in which the height difference between the left and right subtrees of every node is at most a fixed value. This balance ensures that the tree stays balanced in height, preventing it from becoming too tall and narrow like a degenerate tree, which maintains efficient performance for operations.

There are three operations of balanced binary trees, such as search, insert, and delete, which have logarithmic time complexity, i.e., O(log n).

Key Properties of Balanced Binary Trees:

• The heights of the left and right subtrees of any node do not differ from each other by more than a constant, often just 1. 
• They maintain the balance of the overall tree height proportional to log⁡ n, where n is the number of nodes. 
• The operations such as searching, inserting, and deleting elements are done in O(log ⁡n) time complexity in the worst case. 
• Balanced tree structures will prevent the tree from degrading into a degenerate tree, where operations will begin to take O(n) time.

Example of a Balanced Binary Tree:

Here,

• Every node’s left and right subtrees differ in height by at most 1.
• The tree height is minimal for the number of nodes.

Some common self-balancing binary trees in data structures include:

• AVL Tree: If you insert or delete a node from the tree, it will automatically rotate nodes in a way to make sure that the tree keeps its balance (the difference must be less than or equal to 1).
• Red-Black Tree: A tree that uses properties of color and rotations to keep balance, with approximate height of 2log⁡n.
• B-Trees and B+ Trees: Used in database tables and file systems, they generalize balancing to trees with more than 2 children (multi-way trees).
• Splay Tree: A half-balanced tree that uses a process called splaying to keep the frequently accessed nodes between the root and the children.

Build expertise in C and Data Structures with practical projects.

Get Certified in C and Data Structures! Enroll today!

Explore Program

Binary Tree Traversal

The binary tree traversal is the process of visiting each node in a binary tree exactly once in a particular order. Traversing a binary tree helps to perform operations such as searching, printing, or modifying the tree. There are two main categories of traversing in which a binary tree can be traversed: Depth-First Traversal (DFT) and Breadth-First Traversal (BFT).

1. Depth-First Traversal (DFT)

In depth-first traversal, we explore as far as possible along each branch before backtracking. There are three main types of depth-first traversal: inorder, preorder, and postorder. 

Now, let’s discuss each of the binary tree traversal methods in brief with an example:

a. Binary Tree Inorder Traversal

During binary tree inorder traversal, the nodes are visited in the following order: left subtree -> root node -> right subtree.

Pseudocode for Inorder Traversal:

FUNCTION inorder(root):
    IF root IS NOT NULL:
        inorder(root.left)
        PRINT root.value
        inorder(root.right)

Example: 

Inorder traversal: 5 10 12 15 20

Steps:

• Go left of 10 -> visit 5.
• Back to 10 -> visit 10.
• Go right of 10 -> go left of 15 -> visit 12 -> back to 15 -> visit 15 -> go right of 15 -> visit 20.

b. Binary Tree Preorder Traversal

In binary tree preorder traversal, the nodes are visited in this order: root node -> left subtree -> right subtree.

Pseudocode for Preorder Traversal:

FUNCTION preorder(node):
    IF node IS NOT NULL:
        PRINT node.value
        preorder(node.left)
        preorder(node.right)

Example:

Preorder traversal: 1 2 4 5 3

Steps:
Visit 1 -> go left ->visit 2 -> go left -> visit 4 -> back to 2 -> go right -> visit 5 -> back to 1 -> go right -> visit 3.

c. Binary Tree Postorder Traversal

In binary tree postorder traversal, the nodes are visited in this order: left subtree -> right subtree -> root node.

Pseudocode for Postorder Traversal:

FUNCTION postorder(node):
    IF node IS NOT NULL:
        postorder(node.left)
        postorder(node.right)
        PRINT node.value

Example:

Postorder traversal: 5 12 20 15 10

Steps:

• Left of 10 -> visit 5
• Right of 10 -> left of 15 -> visit 12 -> right of 15 -> visit 20 -> back to 15-> visit 15
• Back to 10 -> visit 10

2. Breadth-First Traversal (BFT)

In breadth-first traversal, nodes are visited level by level from top to bottom, left to right, using a queue.

Level Order Traversal in a Binary Tree

In level-order traversal, the nodes of a binary tree are visited level by level from top to bottom, and from left to right within each level. This traversal is also known as Breadth-First Traversal (BFS), since it explores nodes level by level, breadth-wise.

Level Order Traversal Algorithm:

1. Create a queue and enqueue the root node.
2. While the queue is not empty:
   • Dequeue the front node.
   • Process (visit) the node.
   • Enqueue its left child, if it exists.
   • Enqueue its right child, if it exists.

Pseudocode for Level Order Traversal:

FUNCTION level_order(root):
    IF root IS NULL:
        RETURN

    CREATE empty queue
    ENQUEUE root

    WHILE queue IS NOT empty:
        node ← DEQUEUE
        PRINT node.value

        IF node.left IS NOT NULL:
            ENQUEUE node.left
        IF node.right IS NOT NULL:
            ENQUEUE node.right

Example:

Level order traversal: 1 2 3 4 5 6

Level order steps:

1. Start with 1 -> output: 1
2. Next level: 2, 3 -> output: 2 3
3. Next level: 4, 5, 6 -> output: 4 5 6

Binary Tree Operations

Insertion, deletion, searching, and traversal are the four main binary tree operations. Let’s discuss each of them in brief with examples.

1. Insertion

Insertion is the process of adding a new node to the binary tree. In a binary tree, a new node is inserted at the first unoccupied position that is encountered during a level-order traversal. This approach makes sure that the binary tree remains complete.

Pseudocode for Insertion:

FUNCTION insert(root, key):
    IF root IS NULL:
        RETURN new Node(key)
    
    CREATE empty queue
    ENQUEUE root

    WHILE queue is NOT empty:
        node <- DEQUEUE queue
        
        IF node.left IS NULL:
            node.left <- new Node(key)
            RETURN root
        ELSE:
            ENQUEUE node.left
        
        IF node.right IS NULL:
            node.right <- new Node(key)
            RETURN root
        ELSE:
            ENQUEUE node.right

Example:

Let’s insert the value 9 into the following binary tree:

The first available position in level order is the right child of node 4 (since node 4 has a left child but no right child). So, insert 9 as the right child of 4.

After insertion, the binary tree becomes:

2. Deletion

Deletion is the process of removing a node from the binary tree. In a binary tree, when a node is deleted to maintain its structure, the node is replaced with the deepest and rightmost node.

Pseudocode for Deletion:

FUNCTION delete(root, key):
    IF root IS NULL:
        RETURN NULL

    IF root IS a leaf AND root.value = key:
        RETURN NULL

    CREATE empty queue
    ENQUEUE root

    WHILE queue is NOT empty:
        node <- DEQUEUE queue
        IF node.value = key:
            target <- node
        IF node.left:
            ENQUEUE node.left
        IF node.right:
            ENQUEUE node.right

    REPLACE target.value WITH deepestRightmostNode.value
    DELETE deepestRightmostNode

    RETURN root

Example:

Let’s delete the value 4 from this binary tree:

The deepest and rightmost node is 5, so replace node 4 with 5’s value, and then remove the original node 5.

After insertion, the binary tree becomes:

3. Search

Searching is the process of finding a node with a given target value in the binary tree. A node in a binary tree can be searched with any traversal method, such as in-order, post-order, and pre-order.

Pseudocode for Searching:

FUNCTION search(root, key):
    IF root IS NULL:
        RETURN False
    IF root.value = key:
        RETURN True
    
    RETURN search(root.left, key) OR search(root.right, key)

Example:

Let’s search for the value 1 in this binary tree:

Using level-order traversal:

• Visit node 6 
• Visit node 3 
• Visit node 9 
• Visit node 7 
• Visit node 11 

Since traversal is completed without finding 1, thus, the search fails, and the result is that the node does not exist in this tree.

4. Traversal

Traversing is the process of visiting all nodes of the binary tree in a particular order. The main traversal methods are:

• In order (Left, Root, Right)
• Pre-order (Root, Left, Right)
• Post-order (Left, Right, Root)
• Level-order (Breadth-First)

Example:

For this binary tree:

• In-order (Left, Root, Right): 2, 5, 6, 7, 8
• Pre-order (Root, Left, Right): 5, 2, 7, 6, 8
• Post-order (Left, Right, Root): 2, 6, 8, 7, 5
• Level-order (Breadth-First): 5, 2, 7, 6, 8

Implementation of Binary Tree in Data Structure

We have discussed all the basic concepts and operations of the binary tree in data structures. Here is the implementation of a binary tree in data structures in C, C++, Python, and Java.

1. Implementation of Binary Tree in Data Structure in C

Output:

The above program shows the implementation of a binary tree in C programming using level-order insertion to insert elements and a custom queue to look up the target node. The levelOrderInsert function places new nodes at the first available position, and the search function recursively checks whether a target value “30” is in the tree, or not. The main function demonstrates inserting nodes and searching for particular values in the tree.

2. Implementation of Binary Tree in Data Structure in C++

Output:

The above program shows the implementation of a binary tree in C++ programming with the help of level-order insertion and searching for the target node. The levelOrderInsert function adds new nodes at the first available position, and the search function checks whether the target node exists or not. Then, the inorder function performs an inorder traversal to print the tree’s nodes to the console.

3. Implementation of Binary Tree in Data Structure in Python

Output:

The above program shows the implementation of a binary tree in Python programming, in which a binary tree is created with level-order insertion using a deque for efficient node placement. The level_order_insert function adds notes at the first empty position to keep the tree complete, and the search function checks for the key in the tree. Then, inorder function prints the nodes of the tree to the console. 

4. Implementation of Binary Tree in Data Structure in Java

Output:

The above program shows how to implement a binary tree in Java programming language with level-order insertion, using a queue to ensure new nodes are added in the first available position in the binary tree, as well as searching for whether a value in the tree exists or not using the search method. And then the binary tree is traversed, and the nodes of the tree are printed to the console using an inorder traversal.

Master Data Structures and Algorithms with hands-on C programming.

Join the Free DSA Course Today!

Explore Program

Binary Tree Time and Space Complexity Analysis

Here is a brief description of the time and space complexity of a binary tree in data structure. 

1. Time Complexity of Binary Tree

The time complexity of the fundamental operations in a binary tree is dependent on the height of the tree. The height of a binary tree can be O(n) in the worst case because it is possible for a binary tree not to be balanced (therefore, each of the basic operations can take linear time in the number of nodes). Hence, binary trees have O(n) time complexity in the worst case (without being balanced). In the best case, with a perfectly balanced binary tree, the height is O(log n), and those operations can be done in logarithmic time.

2. Space Complexity of Binary Tree

The space complexity of a binary tree arises from two sources: the memory used to store the nodes and the additional space required by the recursive operations (like traversals). Hence, the space you need to store every node will be O(n) since the storage of each node requires memory.

Here is a table that shows the time and space complexity of a binary tree in data structure:

Here, 

• n = number of nodes in the binary tree.
• h = height of the binary tree.

Advantages of Binary Tree

1. Efficient Storage of Hierarchical Data: A binary tree is meant to represent and store hierarchical data in a structured way, specifically for storing data in hierarchical structures, such as charts, file systems, and expression trees.
2. Ease of Insertion and Deletion: In binary trees, we can add to or remove from our data structure without shifting a large number of elements.
3. Efficient Operations: Depending on the balance of a binary tree, we may use balanced trees that are efficient, such as AVL trees or Red-black trees, which allow for balanced operations over our data structure.
4. Supports Effective Traversals: A binary tree supports several different traversal orders, which provide flexible processing of nodes to search.
5. Memory Efficiency: The binary tree does not need memory blocks right next to each other as arrays, and each of its nodes can be stored anywhere we have memory to store them, so they are memory efficient.
6. Supports Efficient Implementation of Recursive Algorithms: The recursive nature of binary trees makes searching, traversing, or manipulating easy to implement.

Disadvantages of Binary Tree

• Can Become Unbalanced: A binary tree can easily become unbalanced if new nodes are added in a sorted order, which turns it into a skewed structure like a linked list. Due to this, height is increased, and efficiency is reduced in searching, inserting, and deleting nodes.
• Gives Inefficient Performance in Worst-Case: In the worst-case scenario, a binary tree can have a time complexity of O(n) for operations such as search or insert, which is no better than a simple linked list.
• Difficult to Maintain Balance: Keeping a binary tree balanced manually is complicated and needs additional algorithms, and if it is not balanced, performance can degrade significantly.
• Difficult Deletion Process: Deleting a node, especially a node that has two children, can be very complex and needs careful rearrangement of the tree, which makes the implementation more complex than linear data structures.
• Memory Overhead: In a binary tree, each node stores additional pointers, which increases memory usage compared to simple arrays or linked lists, especially if the tree has many nodes.

Applications of Binary Tree

1. A binary tree is used in compilers and calculators to parse and evaluate arithmetic or logical expressions.
2. It is ideal for representing parent-child relationships, such as file systems, organizational charts, or structured data formats (XML, JSON).
3. A binary search tree (BST) provides fast searching, insertion, and deletion in databases and indexing systems.
4. The binary tree is implemented by using binary heaps, which are useful for scheduling tasks and algorithms like Dijkstra’s shortest path.
5. Huffman coding tree is used in data compression algorithms such as ZIP or JPEG for efficient encoding of data.
6. A decision tree is widely used in machine learning for tasks like classification, regression, and rule-based decision-making.

Conclusion

A binary tree is a useful structure for storing hierarchical data quickly and allowing for operations such as insertion, deletion, and traversing. It is a fundamental data structure in computer science and programming. Now, as we discussed, there are a number of advantages and uses for binary trees, but there are also downsides to using binary trees that can make programming more complex. So, by understanding what is binary tree in data structure, types of binary trees, properties, various operations, advantages, and disadvantages, you can use binary trees to solve many types of problems.

Binary Tree in Data Structure – FAQs