Mastering Binary Trees with Python – Finding the Largest Node

Have you ever wondered how the largest value in a complex hierarchy is identified with precision and efficiency? Imagine searching for the highest score in a gaming leaderboard or determining the largest data packet in a network. In the world of binary trees, finding the largest node is a fascinating journey that combines structure and logic. 

This blog takes you through mastering binary trees using Python, unraveling their foundational terminologies, types, and the steps to uncover the largest node in a tree. We will also try to visualize a binary tree to grasp its fundamentals before solving intricate and complex problems of data structure and algorithms using Python.

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.

Finding the largest node in a Binary Tree

To demonstrate how to find the largest node, let’s first create and build the binary tree as specified. The code is given as below:- 

"""
Using Python write a python to Create a Binary Tree whose Root Node is 252.
Under Root Node there will be two child nodes 21 and 56.
Now, insert node 49 and 98 inside node 21 and 189 and 1 inside node 56.
Under node 1 insert node 22 and 41 and under node 49 insert node 102 and 103.
Find the largest node or element from the binary tree.
"""


class Node:
    def __init__(self, val):
        self.val = val
        self.right = None
        self.left = None


class SumanBinaryTree:
    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)


     # Method to find the largest node
    def find_largest_node(self, node):
        if node is None:
            return None


        largest = node.val
        left_largest = self.find_largest_node(node.left)
        right_largest = self.find_largest_node(node.right)


        if left_largest and left_largest > largest:
            largest = left_largest
        if right_largest and right_largest > largest:
            largest = right_largest


        return largest


# Create the binary tree
tree = SumanBinaryTree()
tree.insert_node(252)
tree.insert_node(21)
tree.insert_node(56)
tree.insert_node(49)
tree.insert_node(98)
tree.insert_node(189)
tree.insert_node(1)
tree.insert_node(22)
tree.insert_node(41)
tree.insert_node(102)
tree.insert_node(103)


# Print the tree
tree.print_tree(tree.root)


# Find the largest node
largest_node = tree.find_largest_node(tree.root)
print("Largest node:", largest_node)

Now, let us understand the code and work with it.

Step 1: Define the Node Class

The Node class represents a single node in the binary tree.

__init__ method: The constructor initializes a node with a value (val) and two child pointers (right and left) set to None.

Step 2: Define the SumanBinaryTree Class

The SumanBinaryTree class represents the binary tree and contains methods to insert nodes and perform various operations.

• __init__ method: Initializes the root of the tree to None.
• insert_node method: Inserts a new node into the tree. If the tree is empty (root is None), it creates the root node. Otherwise, it calls the private method __insert__recursive to insert the node recursively.

Recursive Insertion

The __insert__recursive method handles the recursive insertion of nodes.

• If the data is less than the current node’s value (node.val), it attempts to insert it into the left subtree. If the left child is None, it creates a new node there. Otherwise, it recurses into the left child.
• Similarly, if the data is greater than or equal to the current node’s value, it follows the same logic for the right subtree.

Printing the Tree

The print_tree method prints the binary tree in a structured format.

• It recursively prints the right subtree, current node, and left subtree, resulting in a visual representation of the tree.

Finding the Largest Node

The find_largest_node method finds the largest node in the binary tree.

• It recursively traverses the tree to find the largest value by comparing the current node’s value with the largest values found in the left and right subtrees and returns the largest of the three.

Creating and Populating the Tree: Let’s create the binary tree and populate it with the specified nodes.

Printing the Tree: We can print the tree structure to visualize it.

Finding the Largest Node: Finally, let’s find and print the largest node in the tree.

Ready to master Python and unlock endless career opportunities in tech? GUVI’s Python Course is designed for learners of all levels, offering a comprehensive curriculum, hands-on projects, and expert mentorship. This course is designed to equip you with the knowledge and tools to excel in fields like AI, Data Science, and Web Development. Take the first step towards transforming your career with Python!

Conclusion

Mastering binary trees goes beyond understanding their structure, it’s about leveraging their properties to solve real-world problems efficiently. By dissecting the Python implementation step-by-step, we’ve not only uncovered how to find the largest node but also delved into the building blocks of this powerful data structure. So, roll up your sleeves, dive into the code, and transform abstract concepts into tangible solutions!

Frequently Asked Questions