What is Binary Tree Data Structure? How to implement it?

Binary Trees are an essential data structure that are frequently used in computer science and software engineering. A binary tree is a tree data structure in which each node can have up to two children, known as the left child and right child. The children of a node are usually referred to as its sub-nodes. In this article, we will cover the definition of a binary tree, its implementation, and its usage.

Definition of Binary Tree

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left and right child. Binary trees are used to represent hierarchical relationships, and they are often used in computer science to store data that needs to be accessed and searched quickly.

Types of Binary Trees

There are different types of binary trees based on the number of sub-nodes a node can have. The most common types are:

Full binary tree: Each node in the tree has either 0 or 2 children. In other words, each node is either a leaf node or has two children.
Complete binary tree: A binary tree is called a complete binary tree if all levels are completely filled except possibly the last level, which should have all its nodes to the left side. A complete binary tree is also called a perfect binary tree.
Balanced binary tree: A binary tree is called balanced if the height of the tree is logarithmic with respect to the number of nodes in the tree.

Binary Tree Implementation

A binary tree can be implemented using either arrays or linked lists. In the case of arrays, we need to keep track of the position of each node in the array. In the case of linked lists, we use nodes that have pointers to their left and right sub-nodes.

Here is an example of how to implement a binary tree using linked lists:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
class BinaryTree:
    def __init__(self, root):
        self.root = Node(root)
        
    def print_tree(self, traversal_type):
        if traversal_type == "preorder":
            return self.preorder_print(tree.root, "")
        
    def preorder_print(self, start, traversal):
        if start:
            traversal += (str(start.value) + "-")
            traversal = self.preorder_print(start.left, traversal)
            traversal = self.preorder_print(start.right, traversal)
        return traversal

In the example above, we have created two classes, Node and BinaryTree. The Node class represents a node in the binary tree, while the BinaryTree class represents the binary tree as a whole. The BinaryTree class has a root attribute that stores the root node of the tree.

We have also defined a print_tree() method that takes a traversal_type parameter, which is used to specify the type of traversal that we want to perform on the tree. In this example, we have only implemented the preorder traversal, which visits the root node, then the left sub-tree, and finally the right sub-tree.

The preorder_print() method is a recursive function that performs the actual traversal. It takes a start parameter, which is the node that we want to start the traversal from, and a traversal parameter, which is the string that we are using to store the traversal path. The method visits each node in the tree and appends its value to the traversal string. It then recursively calls itself with the left and right sub-nodes of the current node.

Insertion Operation on Binary Tree

Inserting a new node into a binary tree involves finding a suitable position for the new node based on its value. We start by comparing the value of the new node with the value of the root node. If the new node’s value is less than the root node’s value, we recursively insert it into the left subtree of the root node. Otherwise, we recursively insert it into the right subtree of the root node.

Let’s take an example to understand the insertion operation better. Consider the following binary tree:

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80

Suppose we want to insert a new node with a value of 45 into this binary tree. We start by comparing 45 with the root node’s value, which is 50. Since 45 is less than 50, we move to the left subtree. We then compare 45 with the value of the node 30. Since 45 is greater than 30, we move to the right subtree of node 30. We then compare 45 with the value of the node 40. Since 45 is less than 40, we have found the position to insert the new node. We insert the new node as the right child of the node 40, resulting in the updated binary tree:

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80
       \
        45

Traversal Operations on Binary Tree

Traversing a binary tree means visiting every node of the tree exactly once in a specific order. There are three popular methods for traversing a binary tree: inorder, preorder, and postorder.

Inorder Traversal

In inorder traversal, we first visit the left subtree, then the root node, and then the right subtree. In other words, we visit the nodes in ascending order of their values.

Let’s take the same example binary tree and traverse it using inorder traversal. The resulting traversal order is 20, 30, 40, 45, 50, 60, 70, 80.

Preorder Traversal

In preorder traversal, we first visit the root node, then the left subtree, and then the right subtree.

Using the same example binary tree and traversing it using preorder traversal, the resulting traversal order is 50, 30, 20, 40, 45, 70, 60, 80.

Postorder Traversal

In postorder traversal, we first visit the left subtree, then the right subtree, and then the root node.

Using the same example binary tree and traversing it using postorder traversal, the resulting traversal order is 20, 45, 40, 30, 60, 80, 70, 50.

Conclusion

Binary trees are an essential data structure used in various computer science applications. They provide an efficient way to store and retrieve data in a sorted order. Binary trees can be used for many different types of problems such as searching, sorting, and graph traversal algorithms. By understanding the basic concepts of binary trees, we can build more complex and efficient data structures and algorithms.

Tagged data structures and algorithms