Python Binary Trees

Python Binary Trees

A Binary Tree is a specific type of tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

This simple constraint leads to a wide variety of useful properties and algorithms. Binary trees are the foundation for more complex structures like Binary Search Trees, Heaps, and AVL Trees.

Implementing a Binary Tree

Similar to a generic tree, we start by defining a Node class. However, instead of a list of children, we'll have specific attributes for left and right.

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

// --- Usage ---
// Create the root
root = Node(1)
// Create children
root.left = Node(2)
root.right = Node(3)
// Create grandchildren
root.left.left = Node(4)
root.left.right = Node(5)
print("Root node:", root.val)
print("Left child of root:", root.left.val)
print("Left-left grandchild:", root.left.left.val)

The structure created above looks like this:

    1
   / \
  2   3
 / \
4   5

Tree Traversal

Traversal is the process of visiting (checking or updating) each node in a tree data structure, exactly once. Unlike linear data structures (Array, Linked List, etc.) which have only one logical way of traversal, trees can be traversed in different ways.

The three most common traversal methods for a binary tree are:

1. In-order Traversal: (Left, Root, Right)
2. Pre-order Traversal: (Root, Left, Right)
3. Post-order Traversal: (Left, Right, Root)

def inorder_traversal(root):
    if root:
        // First recur on left child
        inorder_traversal(root.left)
        // Then print the data of node
        print(root.val, end=" "),
        // Now recur on right child
        inorder_traversal(root.right)

// Using the tree from the previous example
print("In-order traversal:")
inorder_traversal(root) // Output: 4 2 5 1 3