EDUCBA Logo

EDUCBA

MENUMENU
  • Explore
    • EDUCBA Pro
    • PRO Bundles
    • Featured Skills
    • New & Trending
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Log in
  • Sign Up
Home Data Science Data Science Tutorials Data Structures Tutorial Binary Tree in Data Structure
 

Binary Tree in Data Structure

Updated March 6, 2023

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’s 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.

Watch our Demo Courses and Videos

Valuation, Hadoop, Excel, Mobile Apps, Web Development & many more.

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.

Binary Tree in Data Structure 1

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 on 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 in its proper location, and the node location is based on the key value of the node.

Search Operation:

When we need to search for 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 the key value, then we perform a search on 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.

Illustration of Binary Tree

Methods of binary trees are 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.

Binary Tree in Data Structure 2

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.

Complete

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.

Perfect

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.

Degenerate

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 sides of the tree, differ by at most 1. The balanced binary we illustrated by using the following figure as follows.

Balanced Binary Tree

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 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.

different operations

Conclusion

We hope from this article, you have learned the Binary tree in a data structure. We have learned the basic syntax of the Binary tree, and we also see different examples of the Binary tree. We also 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 the definition, syntax, How Binary tree works in data structure?, Different types of binary tree, and 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

Primary Sidebar

Footer

Follow us!
  • EDUCBA FacebookEDUCBA TwitterEDUCBA LinkedINEDUCBA Instagram
  • EDUCBA YoutubeEDUCBA CourseraEDUCBA Udemy
APPS
EDUCBA Android AppEDUCBA iOS App
Blog
  • Blog
  • Free Tutorials
  • About us
  • Contact us
  • Log in
Courses
  • Enterprise Solutions
  • Free Courses
  • Explore Programs
  • All Courses
  • All in One Bundles
  • Sign up
Email
  • [email protected]

ISO 10004:2018 & ISO 9001:2015 Certified

© 2025 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA Login

Forgot Password?

🚀 Limited Time Offer! - 🎁 ENROLL NOW