Binary Tree in Data Structure

Definition of Binary Tree in Data Structure

Data structure provides the different types of trees to the user and we can utilize them as per the user requirement. The binary tree is one tree type in the data structure; it is a special type of tree. In a binary tree, every node or every vertex has two child nodes or single child nodes, or no child node. Basically, a binary tree is a very important class in a data structure in which nodes of a binary tree have at most two children nodes. In the binary tree, the left side is called the left child node and the right side of the binary tree is called the right child node.

Syntax:

struct b_node
{
int item;
struct b_node *left_node;
struct b_node *right_node;
};

Explanation

In the above syntax we represent a binary tree, here we use structure to represent the binary tree that contains two pointers with two items, one for the left child node and one for the right child node as shown in the above syntax.

How Binary tree works in data structure?

Now let’s see how a binary tree works in a data structure as follows.

In above show the binary tree; see here above tree contains at most two child nodes as shown in the above figure. Some important terms are used in binary trees as follows.

Path: Path is used to represent the sequence of nodes either the left side or right side.

Root: The topmost node of the tree we call a root node and each tree has only one root node for example A is a root node.

Parent: We can consider any node as a parent node except the root node for example B as a parent node.

Child: Below parent node tree contains the child node for example D and E is a child node of B.

Leaf: In a binary tree the node does not have any child node that node we called a leaf node for example D.
Subtree: binary we contain the subtree for example in the above binary we show the subtree by using the square.

Keys: It is used to represent the value of a node and that is used to perform the search and insert operation.
Now let’s see the basic operation of the Binary tree as follows.

Insert Operation:

Binary tree representation starts with the insertion operation. After that, we insert the node on its proper location and the node location is based on the key value of the node.

Search Operation:

When we need to search an element in the binary tree, then we start the searching from the root node and then compare the item value or element value with key values. If the search value is less than the key value, then we perform the search on the left side and if the search value is greater than key value then we perform a search at the right side.

Preorder Traversal:

We traverse the node in a pre-order manner as per requirement.

Inorder Traversal:

We traverse the node in an in-order manner as per requirement.

Postorder Traversal:

We traverse the node in a post-order manner as per requirement.

Different Types of Binary Tree

Different types of a binary tree as follows.

1. Full or strict or proper Binary tree

The full binary means if each node should have been 0 or 2 child nodes then we say that this tree is a full binary tree and full binary we can also call it a strict binary tree. The simple example of a full binary tree we illustrated by using the following figure as follows.

2. Complete Binary tree

The complete binary tree is a tree where every one of the nodes is totally filled with the exception of the last level. In the last level, every one of the nodes should be just about as left as could be expected. In a complete binary tree, the nodes should be added from the left side. The complete binary tree is illustrated by using the following figure as follows.

3. Perfect Binary Tree

In a perfect binary tree if all internal nodes have 2 children nodes and all leaf nodes have the same level then we can say this tree is a perfect binary tree. The perfect binary we illustrated by using the following figure as follows.

4. Degenerate Binary Tree

The degenerate binary tree means all internal nodes have only one child node either the left side or the right side of the tree. The degenerate binary tree we illustrate by using the following figure as follows.

The above tree has only one child node and it is also called a right-skewed tree. Similarly, we can draw the left-skewed tree.

5. Balanced Binary Tree:

The balanced tree means both sides of the tree that is left and right side of the tree differ by at most 1. The balanced binary we illustrated by using the following figure as follows.

Example

Now let’s see the example of a binary tree in a data structure as follows.

class B_Node:
def __init__(self, key_value):
self.left_B = None
self.right_B = None
self.val_B = key_value
def PreOrder_B(self):
print(self.val_B, end=' ')
if self.left_B:
self.left_B.PreOrder_B()
if self.right_B:
self.right_B.PreOrder_B()
def InOrder_B(self):
if self.left_B:
self.left_B.InOrder_B()
print(self.val_B, end=' ')
if self.right_B:
self.right_B.InOrder_B()
def PostOrder_B(self):
if self.left_B:
self.left_B.PostOrder_B()
if self.right_B:
self.right_B.PostOrder_B()
print(self.val_B, end=' ')
root = B_Node(4)
root.left_B = B_Node(3)
root.right_B = B_Node(5)
root.left_B.left_B = B_Node(1)
print("Pre-order is: ", end="")
root.PreOrder_B()
print("\nIn order is: ", end="")
root.InOrder_B()
print("\nPost order is: ", end="")
root.PostOrder_B()

Explanation

In the above example, we use a python programming language to implement the binary tree in the data structure. In this example, we implement three different operations a pre-order tree traversal, in-order tree traversal, and postorder tree traversal as shown in the above program. The final output of the above statement we illustrate by using the following snapshot.

Conclusion

We hope from this article you learn the Binary tree in a data structure. From the above article, we have learned the basic syntax of the Binary tree and we also see different examples of the Binary tree. From this article, we learned how and when we use the Binary tree in a data structure.

Recommended Articles

This is a guide to Binary Tree in Data Structure. Here we discuss Definition, syntax, How Binary tree works in data structure?, Different types of binary tree, examples with code implementation. You may also have a look at the following articles to learn more –

1. Heap Data Structure
2. Hashing in Data Structure
3. B+ Tree in Data Structure
4. Linked List in Data Structure