5 Best Ways to Implement a Binary Tree using a Linked List in Python

Rate this post

πŸ’‘ Problem Formulation: Binary trees are fundamental data structures in computer science, often used to implement databases, filesystems, and more. Implementing a binary tree using a linked list in Python requires that each node contains data and references to its left and right child nodes. The input could be a sequence of values, and the desired output is a binary tree where these values are stored as node data, structured according to binary tree properties.

Method 1: Using Class Definitions

This method involves defining a Node class and a BinaryTree class. The Node class holds the value and pointers to left and right children. The BinaryTree class manages the tree and implements functions like insert and traversal. This method provides a clear structure and foundation for building additional tree functionalities.

Here’s an example:

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

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_recursive(node.right, value)

# To create a binary tree and insert values:
tree = BinaryTree()
tree.insert(10)
tree.insert(5)
tree.insert(15)

Output: A binary tree is created with 10 as the root, 5 as the left child of root, and 15 as the right child of root.

This code snippet creates a binary tree from the given inputs, inserting nodes in the appropriate left or right position based on their value. The insert operation is performed recursively within the BinaryTree class, maintaining the properties of a binary search tree.

Method 2: Recursive Insert with a Standalone Function

In this method, we create only a Node class and handle insertion with a standalone recursive function that takes a node and a value to be inserted. This is less structured than the previous method but reduces the complexity by removing the need for a tree management class.

Here’s an example:

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

# To create a binary tree and insert values:
root = insert(None, 10)
insert(root, 5)
insert(root, 15)

Output: A binary tree with root 10, left child 5, and right child 15.

This example uses a simple Node structure to which we add values by calling a standalone function. The function is designed to be used recursively to find the correct position for each new node.

Method 3: Iterative Insert

An iterative approach to constructing a binary tree can sometimes be more intuitive and easier to follow, especially for those less comfortable with recursion. This approach uses while-loops to traverse the tree and determine the proper insertion point for a new node.

Here’s an example:

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

def insert(root, value):
    if root is None:
        return Node(value)
    current = root
    while True:
        if value < current.value:
            if current.left is None:
                current.left = Node(value)
                break
            current = current.left
        else:
            if current.right is None:
                current.right = Node(value)
                break
            current = current.right
    return root

# To create a binary tree and insert values:
root = insert(None, 10)
insert(root, 5)
insert(root, 15)

Output: A binary tree with root 10, left child 5, and right child 15.

This code snippet relies on iteration to insert a new node into the appropriate place in the binary tree. It traverses the tree using a while-loop, checking node values until it finds the correct position for the new node.

Method 4: Insertion with Parent Pointer

Another variant to construct a binary tree using linked lists includes keeping a parent pointer within each node. This method has a significant advantage during node deletion or in operations where access to the parent node is beneficial.

Here’s an example:

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
        root.left.parent = root
    else:
        root.right = insert(root.right, value)
        root.right.parent = root
    return root

# To create a binary tree and insert values:
root = insert(None, 10)
insert(root, 5)
insert(root, 15)

Output: A binary tree with root 10, left child 5 with parent 10, and right child 15 with parent 10.

This code demonstrates the insertion into a binary tree that uses not only the left and right child pointers but also a parent pointer. This makes later operations like node deletions or certain types of tree traversals easier by allowing access to the parent nodes.

Bonus One-Liner Method 5: Pythonic Insert with Function Default Arguments

This Pythonic method leverages default arguments in a function to maintain the state of the parent nodes as we recursively build the tree. It’s an elegant one-liner insert function that keeps the code base minimal and readable.

Here’s an example:

insert = lambda v, root=None: root if v is None else Node(v, insert(v.left), insert(v.right))

# To use this one-liner to create a binary tree:
root = insert(10)
root.left = insert(5)
root.right = insert(15)

Output: A binary tree with root 10, left child 5, and right child 15.

While this is a reduced example for illustrative purposes, the one-liner function represents a Pythonic approach to defining an insert operation that could be extended to check and set the appropriate left or right child nodes within a more complete implementation.

Summary/Discussion

Method 1: Class Definitions. Provides a clear structure and is easily extensible. However, it requires more code than other methods.
Method 2: Recursive Insert with Standalone Function. It simplifies the class structure and is quite readable. Its recursive nature might not be as intuitive to some programmers.
Method 3: Iterative Insert. Iterative methods are generally straightforward but may lack the elegance and simplicity of recursive approaches.
Method 4: Insertion with Parent Pointer. Keeps track of parent nodes, which can be very useful, but adds extra complexity to the node structure.
Method 5: Pythonic Insert with Default Arguments. Minimalist and readable, but may not be straightforward for complex implementations or those new to Python.