Binary Tree in Data Structure

Takeaways

A binary tree is the specialized version of the General tree. A binary tree is a tree in which each node can have at most two nodes.

Complexity of Binary Tree

• Time complexity:- $O(n)$
• Space complexity:- $O(n)$

What is Binary Tree in Data Structure?

Imagine that your college is going to organize a fest, and you are given the responsibility of managing the entire event. Would you do all the work on your own or are you likely to divide the entire team into smaller parts and assign a task to each one of them? In this case, the second option seems to be a better one. You can divide the team into smaller teams like sponsorship, technical, etc., and each team can have a leader who would instruct the other members of the team.

Notice that doing this would create a hierarchical structure where you are the person at the top, then at the second level you have team leaders, and at the third level, each team has some volunteers. This is what trees are! There is only one element at the top, and each element has some children and grandchildren.

A binary tree is a tree data structure(we shall add a link to the tree article here) whose all nodes have either zero, one, or at most two children nodes. These two children are generally referred to as left and right children respectively.

The top-most node is known as the root node, while the nodes with no children are known as leaf nodes.

Notice how the nodes A, B & C contain at most two child nodes. Therefore, the above-given diagram represents a binary tree.

Each node in a binary tree has these three elements –

1. Data item that is the data stored in the node
2. Address of the left child
3. Address of the right child

Terminologies in Binary Tree in Data Structure

1. Nodes – Nodes are the building blocks of any data structure. They majorly contain some data and link to the next/previous nodes. In the case of binary trees, they contain the address of the left and the right child respectively.

2. Root – The topmost node in a tree is known as the root node. A tree can have at most one root node.

3. Parent Node – A node (except the root) that has a succeeding node is known as a parent node.

4. Child Node – A node that has a preceding node is known as a child node. A node can be both parent and child depending on the node that is in context.

5. Leaf Node – A node with no children.

6. Internal Node – A node that has at least one child node is known as an internal node.

7. Depth of a Binary Tree – The number of edges from a node in the tree to the root node.

8. Height of a Binary Tree – The number of edges from the deepest node in the tree to the root node.

The following diagram illustrates all the terminologies in a binary tree –

Now let’s discuss some of the properties of a binary tree

Properties of Binary Tree in Data Structure

1. If there are n nodes in a perfect binary tree (we would read more about them), its height is given by – $log n$. This is because, for a given node in a binary tree, there can be at most 2 child nodes. This further drives us to the explanation that at each level or height of a binary tree, the number of nodes will be almost equal to half of the number of nodes present in the next level. To put it simply, in a binary tree, the number of nodes at each level is almost double the number of nodes at the previous level.

It means, for a binary tree with the height h, Total number of nodes, n = $(2 ^ 0) + (2 ^ 1) + (2 ^ 2) + (2 ^ 3) + ….. + (2 ^ (h-1))$

From `mathematical induction, we also know that

$(2 ^ 0) + (2 ^ 1) + (2 ^ 2) + (2 ^ 3) + ….. + (2 ^ {(h-1)}) = (2 ^ h)-1$

Therefore,

$(2 ^ h)-1 = n => 2 ^ h = n + 1 => h = log2(n+1)$

Therefore, the minimum height of a binary tree is almost equal to log(n).

2. The minimum number of nodes possible at the height h of a binary tree is given by h+1.

3. If a binary tree has L number of leaf nodes, its height is given by L + 1

4. At each level i of a binary tree, the number of total nodes is given by 2 ^ i.

Types of Binary Tree in Data Structure

Binary Trees are of many types, and each of these trees has its own properties and characteristics.

Let’s discuss some of them in detail –

1. Full Binary Tree

A full binary tree, also known as a proper binary tree, is a tree in which each internal node has either zero or two children nodes is known as a full binary tree.

In other words, if in a binary tree a node contains only one child node, it is not a full binary tree.

The following diagrams shows a full binary tree –

Notice how each node has either zero or two children nodes.

In a full binary tree, if there are n number of total nodes –

• The number of internal nodes is given by (n-1)/2
• The number of leaf nodes is given by (n+1)/2

2. Complete Binary Tree

A complete binary tree is a binary tree in which all the elements are arranged without missing any sequence.

In a complete binary tree –

• All the levels are completely filled except the last level that may or may not be completely filled.
• Elements are filled from left to right.

The following trees are complete binary trees since they have no empty spaces in them.

3. Perfect Binary Trees

If in a tree all the internal nodes have exactly two children nodes, it is known as a perfect binary tree.

In a perfect binary tree, all the leaf nodes are on the same level.

The following diagrams represents a perfect binary tree –

Consider a perfect binary tree with height h, the total number of nodes in this case is given by 2h – 1.

4. Degenerate Binary Trees

If in a binary tree each node contains only one child node either on the left side or the right side of the tree, it is known as a degenerate binary tree.

Degenerate binary trees are equal to linked lists in terms of performance. The following tree shows a degenerate binary tree –

Degenerate binary trees can also be classified into two types –

a. Left-skewed – A degenerate binary tree in which all the nodes lean towards the left side of the tree. The following diagram shows a left-skewed degenerate binary tree –

b. Right-skewed – A degenerate binary tree in which all the nodes lean towards the right side of the tree. The following diagram shows a right-skewed degenerate binary tree –

5. Balanced Binary Trees

A binary tree is said to be balanced if the height of the left and the right subtrees differ by 0 or 1.

In a balanced binary tree, both the left and right trees are also balanced. The following diagram shows a balanced binary tree –

Notice that in the first image, the right subtree is at the height of 3, and the left subtree is at 2. The difference between the heights of the left and the right subtree is therefore 1. Therefore, the given tree is a balanced binary tree.

In the second image, the right subtree is at the height of 3, whereas the left subtree is at 1. The difference between the heights of the left and the right subtrees is 2. It violates the condition of a balanced binary tree. Hence, the given tree is not a balanced binary tree.

Now that we know what binary trees are, let’s write some code to implement them.

Implementation of Binary Tree in Data Structure

1. Binary Tree Program in C

2. Binary Tree Program in C++

3. Binary Tree Program in Java

4. Binary Tree Program in Python

Now let’s discuss some benefits of binary trees.

Benefits of Binary Tree in Data Structure

1. Binary trees are used in binary search trees. It helps in searching for elements in a faster and efficient way.

2. Binary trees are also used in heaps that are special kind of binary trees. Heaps are used in heap sort, which is an efficient sorting algorithm. Heaps are also used in building priority queues in which elements are arranged in the order of their priorities.

3. Binary trees are used in converting different prefix and postfix expressions.

4. Binary trees are also used in graph traversal algorithms like Dijkastra’s algorithm.

5. Some real-life applications of binary trees include virtual memory management, and 3D where faster rendering of objects is required.

Binary tree Time Complexity

Searching: Worst case complexity of O(n). Insertion: Worst case complexity of O(n). Deletion: Worst case complexity of O(n).

Binary tree Space Complexity

Searching: O(n). Insertion: O(n). Deletion: O(n).