Binary Trees and Tree Traversals

In the previous lesson, we studied the Bellman–Ford algorithm, which focuses on shortest paths in weighted graphs.

Now we move into an equally important family of data structures: trees.

Trees form the backbone of many algorithms, including searching, indexing, parsing, and decision-making systems. Understanding trees deeply is essential for mastering algorithms.

What Is a Tree?

A tree is a hierarchical data structure consisting of nodes connected by edges.

Unlike graphs, a tree has:

• No cycles
• A single root node
• A unique path between any two nodes

This structure makes trees ideal for representing hierarchical relationships.

What Is a Binary Tree?

A binary tree is a special type of tree where each node has at most two children:

Left child and Right child.

This simple constraint enables powerful algorithms for searching and ordering data.

Key Terminology

Before writing algorithms, we must understand basic tree terminology.

• Root: The topmost node
• Parent: A node that has children
• Leaf: A node with no children
• Height: Longest path from root to leaf

Why Tree Traversals Matter

Tree traversal means visiting every node in a tree in a specific order.

Since trees are not linear structures, there is no single obvious way to traverse them.

Different traversal orders solve different problems.

Types of Tree Traversals

Tree traversals are broadly divided into:

• Depth-First Traversals
• Breadth-First Traversal

In this lesson, we focus on Depth-First Traversals.

Depth-First Traversal Overview

Depth-first traversal explores a tree by going as deep as possible before backtracking.

There are three classic DFS traversals:

• Inorder
• Preorder
• Postorder

Inorder Traversal

In inorder traversal, nodes are visited in this order:

Left → Root → Right

This traversal is especially important for Binary Search Trees, as it retrieves values in sorted order.

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value)
        inorder(node.right)

Preorder Traversal

In preorder traversal, nodes are visited as:

Root → Left → Right

This traversal is useful when copying or serializing a tree structure.

def preorder(node):
    if node:
        print(node.value)
        preorder(node.left)
        preorder(node.right)

Postorder Traversal

In postorder traversal, nodes are visited as:

Left → Right → Root

This traversal is commonly used when deleting or freeing tree nodes.

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value)

Visualizing Traversals

Consider this binary tree:

    A
   /  \\
  B    C
 / \\
D  E

Traversal results:

• Inorder: D B E A C
• Preorder: A B D E C
• Postorder: D E B C A

Why Multiple Traversals Exist

Each traversal serves a different purpose.

There is no “best” traversal — only the traversal that fits the problem.

Understanding these differences is a common interview requirement.

Time Complexity

All tree traversals visit every node exactly once.

Time complexity:

O(n)

Where n is the number of nodes.

Real-World Applications

Binary tree traversals are used in:

• Expression evaluation
• File systems
• Syntax trees in compilers
• Database indexing

Exercises

Quick Quiz

In the next lesson, we will move deeper into trees by studying Binary Search Trees (BST) and how they enable efficient searching.