Binary Trees & Traversal

A Binary Tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Binary trees are widely used in computer science for searching, sorting, expression parsing, and more.

Types of Binary Tree Traversal

Tree traversal means visiting all the nodes in a tree in a specific order. The most common binary tree traversal methods are:

1. Inorder Traversal (Left, Root, Right)

First visit the left subtree, then the root node, and finally the right subtree.

This traversal returns the nodes in a sorted order for binary search trees (BST).

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

2. Preorder Traversal (Root, Left, Right)

Visit the root node first, then traverse the left subtree followed by the right subtree.

Used to create a copy of the tree or to get prefix expression of an expression tree.

def preorder(root):
    if root:
        print(root.data, end=" ")
        preorder(root.left)
        preorder(root.right)

3. Postorder Traversal (Left, Right, Root)

Traverse the left subtree, then right subtree, and visit the root node last.

Used to delete the tree or get the postfix expression of an expression tree.

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.data, end=" ")

4. Level Order Traversal (Breadth-First)

Visit nodes level by level starting from the root using a queue data structure.

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.data, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Binary Tree Node Definition

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

To use these traversal functions, you first create nodes and link them as a tree.