Back

Binary Tree Traversal

Visualize inorder, preorder, and postorder traversal algorithms on any binary tree structure

Binary Tree

Click node to edit • Right-click to delete

Loading...

Current Operation:

Ready to traverse. Build a tree and select a traversal type, then click "Start" to begin.

Nodes Visited

0

Time Complexity

O(n)

Space Complexity

O(h)

h = tree height (recursion stack)

Tree Size

7

Color Coding:

Currently Visiting
In Call Stack
Visited
Default (not visited)

Traversal Type:

Simulation

SlowFast
800ms

Tree Structure (level-order):

[4, 2, 6, 1, 3, 5, 7]

Total nodes: 7 | Inorder: [1, 2, 3, 4, 5, 6, 7]

What are Tree Traversals?

Tree traversal is the process of visiting all nodes in a tree in a specific order. For binary trees, there are three main depth-first traversal methods: inorder, preorder, and postorder.

Traversal Types

  • Inorder (Left → Root → Right): Visit left subtree, then root, then right subtree. For BST, this gives values in sorted order.
  • Preorder (Root → Left → Right): Visit root first, then left subtree, then right subtree. Useful for copying tree structure.
  • Postorder (Left → Right → Root): Visit left subtree, then right subtree, then root. Useful for deleting trees.

Implementation

1. Inorder Traversal

Left → Root → Right (gives sorted order for BST):

from typing import List, Optional

class TreeNode:
    """Binary tree node structure."""
    def __init__(self, value: int, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.value = value
        self.left = left
        self.right = right

def inorder_traversal(root: Optional[TreeNode]) -> List[int]:
    """
    Perform inorder traversal: Left → Root → Right.
    
    Visits nodes in sorted order for a BST. Useful for getting values
    in ascending order.
    
    Args:
        root: Root node of the binary tree (can be None for empty tree).
    
    Returns:
        List of node values in inorder traversal order.
    
    Time Complexity: O(n) where n is number of nodes.
    Space Complexity: O(h) where h is tree height (for recursion stack).
    """
    result: List[int] = []
    
    def inorder(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        inorder(node.left)   # Visit left subtree
        result.append(node.value)  # Visit root
        inorder(node.right)  # Visit right subtree
    
    inorder(root)
    return result

# Example
# Tree:       4
#           /   \
#          2     6
#         / \   / \
#        1   3 5   7
# Inorder: [1, 2, 3, 4, 5, 6, 7]

2. Preorder Traversal

Root → Left → Right:

from typing import List, Optional

class TreeNode:
    """Binary tree node structure."""
    def __init__(self, value: int, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.value = value
        self.left = left
        self.right = right

def preorder_traversal(root: Optional[TreeNode]) -> List[int]:
    """
    Perform preorder traversal: Root → Left → Right.
    
    Visits root before children. Useful for copying tree structure or
    prefix expression evaluation.
    
    Args:
        root: Root node of the binary tree (can be None for empty tree).
    
    Returns:
        List of node values in preorder traversal order.
    
    Time Complexity: O(n) where n is number of nodes.
    Space Complexity: O(h) where h is tree height (for recursion stack).
    """
    result: List[int] = []
    
    def preorder(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        result.append(node.value)  # Visit root
        preorder(node.left)   # Visit left subtree
        preorder(node.right)  # Visit right subtree
    
    preorder(root)
    return result

# Example
# Tree:       4
#           /   \
#          2     6
#         / \   / \
#        1   3 5   7
# Preorder: [4, 2, 1, 3, 6, 5, 7]

3. Postorder Traversal

Left → Right → Root:

from typing import List, Optional

class TreeNode:
    """Binary tree node structure."""
    def __init__(self, value: int, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.value = value
        self.left = left
        self.right = right

def postorder_traversal(root: Optional[TreeNode]) -> List[int]:
    """
    Perform postorder traversal: Left → Right → Root.
    
    Visits children before root. Useful for deleting tree nodes or
    postfix expression evaluation.
    
    Args:
        root: Root node of the binary tree (can be None for empty tree).
    
    Returns:
        List of node values in postorder traversal order.
    
    Time Complexity: O(n) where n is number of nodes.
    Space Complexity: O(h) where h is tree height (for recursion stack).
    """
    result: List[int] = []
    
    def postorder(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        postorder(node.left)   # Visit left subtree
        postorder(node.right)  # Visit right subtree
        result.append(node.value)  # Visit root
    
    postorder(root)
    return result

# Example
# Tree:       4
#           /   \
#          2     6
#         / \   / \
#        1   3 5   7
# Postorder: [1, 3, 2, 5, 7, 6, 4]

Time & Space Complexity

Time Complexity:

  • Best/Average/Worst: O(n) - Must visit every node once

Space Complexity: O(h) where h is the height of the tree (for recursion stack). O(log n) for balanced trees, O(n) for skewed trees.

Real-World Applications

  • Expression evaluation: postorder for postfix, inorder for infix
  • Tree copying: preorder traversal preserves structure
  • Tree deletion: postorder ensures children deleted before parent
  • Sorted output: inorder gives sorted order for BST
  • Serialization: converting tree to array/string representation