Introduction to Binary Tree using Python

Introduction

What do file systems, databases, and AI decision trees have in common? They all rely on hierarchical data structures like binary trees. Whether you’re sorting data efficiently, building search algorithms, or managing hierarchical relationships, binary trees are a key tool in a programmer’s arsenal.

At first glance, a binary tree may seem like a simple branching structure. However, its ability to optimize search operations, store sorted data, and represent hierarchical relationships makes it a fundamental concept in computer science. From balancing search efficiency to enabling fast lookups, binary trees power everything from autocomplete features to game AI logic.

In this blog, we’ll explore the foundational aspects of binary trees, understand their structure, and implement them using Python. We’ll also visualize a binary tree, making it easier to grasp its workings before tackling more advanced problems in data structures and algorithms.

Basic Terminology

Before diving deeper it is profoundly crucial to understand the basic terms which are associated with binary trees. Given below is the list of terminologies commonly associated with a binary tree. Before writing any kind of code it would be helpful if you go through the terminologies as this will become the foundation for working with a binary tree.

• Node: The fundamental unit of a binary tree, containing data and references to its child nodes.
  
• Root: The topmost node in a binary tree.
  
• Parent: A node that has one or more child nodes.
  
• Child: A node directly connected to another node when moving away from the root.
  
• Leaf: A node that does not have any children.
  
• Subtree: A tree comprising a node and its descendants.
  
• Height: The length of the longest path from the root to a leaf.
  
• Depth: The length of the path from the root to a given node.

Types of Binary Trees

Binary trees come in various forms each with its own unique properties and applications. Given below are the types of binary trees which are commonly associated with a binary tree. Before writing any kind of code it would be helpful if you go through the terminologies as this will become the foundation for working with types of binary trees.

1. Full Binary Tree: Every node other than the leaves has exactly two children.
   
2. Complete Binary Tree: All levels are fully filled except possibly the last, which is filled from left to right.
   
3. Perfect Binary Tree: All internal nodes have two children, and all leaves are at the same level.
4. Balanced Binary Tree: The difference in height between the left and right subtrees for any node is at most one.
   
5. Degenerate (or Skewed) Binary Tree: Each parent node has only one child, resembling a linked list.
   

Also Read: Mastering Binary Trees with Python – Finding the Smallest Node

Binary Tree Operations

Understanding the working of binary trees requires familiarity with the basic operations that can be performed on them. Here are some operations which we commonly do on a binary tree. Before writing any kind of code it would be helpful if you go through the types of binary tree operations which can be done on a binary tree as this will become the foundation for all sorts of operations which you can perform on it using  intricate and complex problems of Data Structure and Algorithms using Python.

1. Insertion: Adding a node to the tree while maintaining its properties.
   
2. Deletion: Removing a node and adjusting the tree to maintain its properties.
   
3. Searching: Finding a node with a given value.
   

4. Traversal: Visiting all the nodes in a specific order.
   
   • In-order Traversal: Visit the left subtree, root, and right subtree. This traversal yields nodes in non-decreasing order.
     
   • Pre-order Traversal: Visit the root, left subtree, and right subtree. Useful for creating a copy of the tree.
     
   • Post-order Traversal: Visit the left subtree, right subtree, and root. Useful for deleting the tree.
     
   • Level-order Traversal: Visit nodes level by level from left to right. Implemented using a queue.

As mentioned earlier, in this blog we will be constructing a binary tree using Python programming language and try to visualize it on our terminal or command-prompt.

Mastering these operations is crucial for optimizing search functions, improving efficiency, and structuring data effectively. If you’re serious about leveling up your Python skills and working hands-on with real-world implementations of binary trees, GUVI’s Python course is a great place to start. This comprehensive program not only covers the fundamentals but also dives deep into advanced data structures, helping you become a confident problem-solver in coding interviews and development projects.

👉 Explore the Python Course and start building robust algorithms today!

Constructing a Binary Tree using Python

Given below is a simple Python implementation as to how to create a Binary tree. The code will remain the same for its construction and its visualization if you are working with any intricate and complex problem that is associated with a binary tree.

class Node:

    “””

        val : Stores data of Node

        left : Reference to Left Child Node

        right : Reference to Right Child Node

    “””

    def __init__(self, val):

        self.val = val

        self.right = None

        self.left = None

class SumanBinaryTree:

    “””

        root : Reference to the root node of tree

    “””

    def __init__(self):

        self.root = None

    def insert_node(self, data):

        if self.root is None:

            self.root = Node(data)

        else:

            self.__insert__recursive(self.root, data)

    def __insert__recursive(self, node, data):

        if data < node.val:

            if node.left is None:

                node.left = Node(data)

            else:

                self.__insert__recursive(node.left, data)

        else:

            if node.right is None:

                node.right = Node(data)

            else:

                self.__insert__recursive(node.right, data)

    def print_tree(self, node, level=0):        

        if node is not None:

            self.print_tree(node.right, level + 1)

            print(‘ ‘ * 4 * level + ‘->’, node.val)

            self.print_tree(node.left, level + 1)

if __name__ == “__main__”:

    # Creating the binary tree

    tree = SumanBinaryTree()

    tree.root = Node(10)  # Root node

    # Level 1

    tree.root.left = Node(20)

    tree.root.right = Node(30)

    # Level 2

    tree.root.left.left = Node(40)

    tree.root.left.right = Node(50)

    tree.root.right.left = Node(60)

    tree.root.right.right = Node(70)

    # Level 3

    tree.root.right.right.left = Node(80)

    tree.root.right.right.right = Node(90)

    # Print the binary tree

    tree.print_tree(tree.root)

Let’s break down and describe each part of the given code in detail. The code defines a binary tree structure and provides functionality to insert nodes and print the tree.

class Node:

    “””

        val : Stores data of Node

        left : Reference to Left Child Node

        right : Reference to Right Child Node

    “””

    def __init__(self, val):

        self.val = val

        self.right = None

        self.left = None

Description:

• Purpose: The Node class encapsulates the properties and behaviors of each node within a binary tree. Each node stores a value and has references to its left and right child nodes.
  
• Attributes:
  • val: Stores the data of the node.
  • left: Reference to the left child node (initially set to None).
  • right: Reference to the right child node (initially set to None).
    
• Constructor: The __init__ method initializes a new node with the given value and sets its left and right child references to None.

class SumanBinaryTree:

    “””

        root : Reference to the root node of tree

    “””

    def __init__(self):

        self.root = None

    def insert_node(self, data):

        if self.root is None:

            self.root = Node(data)

        else:

            self.__insert__recursive(self.root, data)

    def __insert__recursive(self, node, data):

        if data < node.val:

            if node.left is None:

                node.left = Node(data)

            else:

                self.__insert__recursive(node.left, data)

        else:

            if node.right is None:

                node.right = Node(data)

            else:

                self.__insert__recursive(node.right, data)

    def print_tree(self, node, level=0):        

        if node is not None:

            self.print_tree(node.right, level + 1)

            print(‘ ‘ * 4 * level + ‘->’, node.val)

            self.print_tree(node.left, level + 1)

Description:

• Purpose: The SumanBinaryTree class manages the structure and operations of the binary tree, such as inserting nodes and printing the tree.
• Attributes:
  • root: Reference to the root node of the tree (initially set to None).
• Constructor: The __init__ method initializes an empty binary tree with the root set to None.
  
• Methods:
  • insert_node(self, data): Inserts a node with the given data into the binary tree.
    • If the tree is empty (root is None), the new node becomes the root.
    • Otherwise, it calls the helper method __insert__recursive to insert the node recursively.
  • __insert__recursive(self, node, data): A helper method to insert a node recursively.
    • If the given data is less than the current node’s value, it goes to the left subtree.
    • If the given data is greater than or equal to the current node’s value, it goes to the right subtree.
    • If the appropriate child node is None, it creates a new node with the given data.
  • print_tree(self, node, level=0): Prints the binary tree in a structured format.
    • It recursively prints the right subtree, the current node, and then the left subtree.
    • Uses indentation to represent the level of the tree.

# Main function

if __name__ == “__main__”:

    # Creating the binary tree

    tree = SumanBinaryTree()

    tree.root = Node(10)  # Root node

    # Level 1

    tree.root.left = Node(20)

    tree.root.right = Node(30)

    # Level 2

    tree.root.left.left = Node(40)

    tree.root.left.right = Node(50)

    tree.root.right.left = Node(60)

    tree.root.right.right = Node(70)

    # Level 3

    tree.root.right.right.left = Node(80)

    tree.root.right.right.right = Node(90)

    # Print the binary tree

    tree.print_tree(tree.root)

Description:

• Purpose: This block of code creates a binary tree and demonstrates the insertion and printing of nodes.
  

• Tree Construction:
  • A SumanBinaryTree object tree is created.
  • The root node is initialized with a value of 10.
  • Nodes are inserted manually to build the tree with values at different levels.
  • Level 1 nodes: 20 (left) and 30 (right).
  • Level 2 nodes: 40 (left-left), 50 (left-right), 60 (right-left), 70 (right-right).
  • Level 3 nodes: 80 (right-right-left), 90 (right-right-right).
    
• Printing the Tree:
  • The print_tree method is called to print the structure of the binary tree.

The Output

This format helps visualize the hierarchical structure of the binary tree, showing the relationships between parent and child nodes at different levels.

Feel free to experiment with the code and modify it to further enhance your understanding of binary trees! 🚀😊

Let me know if you need any further assistance or clarifications! 🌳✨

Conclusion

Binary trees are much more than a theoretical concept; they play a critical role in real-world applications, from database indexing to AI-based decision-making systems. Their structured yet flexible nature makes them indispensable in computer science.

By understanding the core principles of binary trees, their types, and how they can be implemented in Python, you’re laying the groundwork for solving complex problems in data structures and algorithms. Mastering these concepts will not only strengthen your understanding of tree-based data structures but also enhance your problem-solving skills in programming.

Now that we’ve built a binary tree in Python and explored its operations, the next step is to apply this knowledge to more advanced scenarios like balanced trees, heaps, and graph-based optimizations. The deeper you dive, the more you’ll see how powerful binary trees can be in computational efficiency.