Binary Trees

Binary Trees

In the previous tutorial, we learned about standard Trees. A normal Tree node can have an infinite number of children.

However, the most famous and widely used tree in Computer Science is the Binary Tree. Let's break down exactly how it works.

1. The "Two Child" Rule

The word "Binary" means two.

In a Binary Tree, a parent node is strictly limited to having:

• 0 children (This is called a Leaf node).
• 1 child (Either Left or Right).
• 2 children (Both Left and Right).

A node can never have 3 or more children!

A Binary Tree: Each node splits into a maximum of two smaller paths.

2. Anatomy of a Binary Tree Node

Under the hood, a Binary Tree Node is very similar to a Doubly Linked List Node.

Instead of pointing "Forward" and "Backward", it points "Left" and "Right".

Every node must store three things:

1. Data: The actual value (e.g., 10).
2. Left Pointer: The memory address of the left child.
3. Right Pointer: The memory address of the right child.

3. Types of Binary Trees

Binary Trees come in a few different "shapes." Knowing these names is very helpful for technical interviews:

Full Binary Tree

• Rule: Every node has either 0 or 2 children.
• There are no nodes with only 1 child allowed!

Complete Binary Tree

• Rule: Every level of the tree is completely filled, except possibly the last level.
• If the last level is not full, the nodes must be pushed as far left as possible.

Perfect Binary Tree

• Rule: Every internal node has exactly 2 children, and all Leaf nodes are on the exact same bottom level.
• It forms a perfect, symmetrical triangle.

4. Traversing a Binary Tree

With an Array, you just loop from index 0 to the end. But how do you "loop" through a Tree?

We use Depth-First Search (DFS) traversals. There are three standard ways to read the data in a Binary Tree:

1. In-Order Traversal

• Order: Left -> Root -> Right
• Use Case: If you use this on a Binary Search Tree, it will print the numbers in perfectly sorted order!

2. Pre-Order Traversal

• Order: Root -> Left -> Right
• Use Case: Great for making a direct copy (clone) of a tree.

3. Post-Order Traversal

• Order: Left -> Right -> Root
• Use Case: Great for safely deleting a tree (you delete the children before you delete the parent).

5. Coding a Binary Tree

First, we need to create our Node class and build the basic structure of the tree.

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

# Create the Root Node
root = Node(10)
# Add Left and Right Children
root.left = Node(5)
root.right = Node(15)
# Add grandchildren
root.left.left = Node(2)
root.left.right = Node(7)

Now, let's write the code for the three different Depth-First Search traversals! Notice how we use Recursion (a function calling itself) to effortlessly walk down the left and right branches.

def inorder_traversal(node):
    # Base case: If the node is None, stop!
    if node is not None:
        # 1. Visit the Left child
        inorder_traversal(node.left)
        # 2. Print the Root (Current Node)
        print(node.data, end=" ")
        # 3. Visit the Right child
        inorder_traversal(node.right)

print("In-Order Traversal:")
inorder_traversal(root)

def preorder_traversal(node):
    if node is not None:
        # 1. Print the Root first
        print(node.data, end=" ")
        # 2. Visit the Left child
        preorder_traversal(node.left)
        # 3. Visit the Right child
        preorder_traversal(node.right)

print("\nPre-Order Traversal:")
preorder_traversal(root)

def postorder_traversal(node):
    if node is not None:
        # 1. Visit the Left child
        postorder_traversal(node.left)
        # 2. Visit the Right child
        postorder_traversal(node.right)
        # 3. Print the Root last
        print(node.data, end=" ")

print("\nPost-Order Traversal:")
postorder_traversal(root)