12.4 Binary and Search Trees in Python

NicePython

— 3 min read

A tree is a hierarchical data structure consisting of nodes connected by edges. The topmost node is called the root, and each node can have zero or more children. A node with no children is called a leaf. Trees are widely used for tasks like representing hierarchical data, implementing search algorithms, and managing sorted data.

A binary tree is a type of tree where each node has at most two children (referred to as left and right).

12.4.1 Binary Tree

In a binary tree, each node has:

  1. Data: The value stored in the node.
  2. Left: A pointer to the left child (which can be None if there’s no left child).
  3. Right: A pointer to the right child (which can be None if there’s no right child).

Example: Implementing a Binary Tree

class TreeNode:
    def __init__(self, data):
        self.data = data  # Value of the node
        self.left = None  # Pointer to the left child
        self.right = None  # Pointer to the right child

class BinaryTree:
    def __init__(self):
        self.root = None  # The root of the tree

    # Insert data into the tree
    def insert(self, data):
        if self.root is None:
            self.root = TreeNode(data)
        else:
            self._insert(self.root, data)

    def _insert(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = TreeNode(data)
            else:
                self._insert(node.left, data)
        else:
            if node.right is None:
                node.right = TreeNode(data)
            else:
                self._insert(node.right, data)

    # In-order traversal of the tree (left -> root -> right)
    def in_order_traversal(self, node):
        if node is not None:
            self.in_order_traversal(node.left)
            print(node.data, end=" ")
            self.in_order_traversal(node.right)

# Example usage
bt = BinaryTree()
bt.insert(5)
bt.insert(2)
bt.insert(8)
bt.insert(1)
bt.insert(3)
bt.in_order_traversal(bt.root)  # Output: 1 2 3 5 8

In this example:

  • The insert() method inserts a new node into the binary tree while maintaining the binary search tree property (left children are smaller, right children are larger).
  • The in_order_traversal() method prints the elements of the tree in sorted order.

Common Tree Traversal Methods:

  1. In-Order (left -> root -> right): Visit the left subtree, the root, and then the right subtree. Used for binary search trees to print values in sorted order.
  2. Pre-Order (root -> left -> right): Visit the root first, followed by the left subtree, then the right subtree.
  3. Post-Order (left -> right -> root): Visit the left subtree, the right subtree, and then the root.

Advantages of Binary Trees:

  • Efficient searching, insertion, and deletion (especially in balanced trees).
  • Useful for hierarchical data structures.

Disadvantages of Binary Trees:

  • Unbalanced trees can lead to inefficient operations (as bad as O(n) in the worst case).

12.4.2 Binary Search Tree (BST)

A **Binary Search Tree (BST

)** is a binary tree that maintains a specific order:

  • For each node, all values in its left subtree are smaller than the node’s value.
  • All values in its right subtree are larger than the node’s value.

This property makes searching efficient because it allows you to ignore half of the tree at each step.

Example: Searching in a Binary Search Tree

class BinarySearchTree(BinaryTree):
    # Search for a value in the tree
    def search(self, data):
        return self._search(self.root, data)

    def _search(self, node, data):
        if node is None or node.data == data:
            return node  # Found the node or reached the end
        if data < node.data:
            return self._search(node.left, data)  # Search left subtree
        return self._search(node.right, data)  # Search right subtree

# Example usage
bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(20)
bst.insert(1)
bst.insert(8)

# Search for a value
found_node = bst.search(8)
if found_node:
    print(f"Node with value {found_node.data} found.")  # Output: Node with value 8 found.
else:
    print("Node not found.")

In this example:

  • search() traverses the tree to find the node with the specified value using the binary search property of BST.

12.4.3 Summary

  • Trees: Hierarchical data structures with nodes connected by edges, used for representing hierarchical relationships or efficiently managing sorted data.
    • Binary Tree: A tree in which each node has at most two children.
    • Binary Search Tree (BST): A binary tree that maintains an ordering where the left subtree contains smaller elements and the right subtree contains larger elements, making searching efficient.

By understanding and implementing trees, you can efficiently solve problems involving dynamic data storage, hierarchical relationships, and sorted data management.

Read more