Visualizers

Tree Traversals Visualizer

Step-through BST traversals: Inorder, Preorder, and Postorder.

native (SVG) Client-side

Traversal Type

Speed

Traversal Output

Select traversal type and click Traverse.

Execution Log

Current Action:

Idle

Complexity Details:

Time: $O(n)$ (Visits every node exactly once)

Space: $O(h)$ (Stack space proportional to tree height)

Binary Tree Traversals

Unlike linear data structures (arrays, linked lists) which have only one logical way to traverse them, trees can be traversed in different ways. Depth-First Traversals are categorized by the order in which the root node is visited relative to its children.

Depth-First Traversal Styles

Inorder (Left, Root, Right): Visited left subtree, then root, then right subtree. For a BST, this visits nodes in ascending order.
Preorder (Root, Left, Right): Visited root first, then left subtree, then right subtree. Useful for copying a tree structure.
Postorder (Left, Right, Root): Visited left subtree, then right subtree, then root. Useful for deleting a tree or evaluating postfix expressions.

Implementation

// Preorder (Root, Left, Right)
function preorder(node) {
  if (!node) return;
  console.log(node.val);
  preorder(node.left);
  preorder(node.right);
}

// Inorder (Left, Root, Right)
function inorder(node) {
  if (!node) return;
  inorder(node.left);
  console.log(node.val);
  inorder(node.right);
}

// Postorder (Left, Right, Root)
function postorder(node) {
  if (!node) return;
  postorder(node.left);
  postorder(node.right);
  console.log(node.val);
}

# Preorder (Root, Left, Right)
def preorder(node):
    if not node:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

# Inorder (Left, Root, Right)
def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

# Postorder (Left, Right, Root)
def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

public class TreeTraversals {
    static class Node {
        int val;
        Node left, right;
    }

    // Preorder (Root, Left, Right)
    public void preorder(Node node) {
        if (node == null) return;
        System.out.println(node.val);
        preorder(node.left);
        preorder(node.right);
    }

    // Inorder (Left, Root, Right)
    public void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.println(node.val);
        inorder(node.right);
    }

    // Postorder (Left, Right, Root)
    public void postorder(Node node) {
        if (node == null) return;
        postorder(node.left);
        postorder(node.right);
        System.out.println(node.val);
    }
}

#include <iostream>

struct Node {
    int val;
    Node* left = nullptr;
    Node* right = nullptr;
};

// Preorder (Root, Left, Right)
void preorder(Node* node) {
    if (!node) return;
    std::cout << node->val << std::endl;
    preorder(node->left);
    preorder(node->right);
}

// Inorder (Left, Root, Right)
void inorder(Node* node) {
    if (!node) return;
    inorder(node->left);
    std::cout << node->val << std::endl;
    inorder(node->right);
}

// Postorder (Left, Right, Root)
void postorder(Node* node) {
    if (!node) return;
    postorder(node->left);
    postorder(node->right);
    std::cout << node->val << std::endl;
}

Related Tools

Big-O Visualizer

Interactive growth-curve chart for common complexity classes.

Data Structure Visualizer

Animated operations on linked lists, trees, stacks and hash tables.

Algorithm Visualizer

Step-through animations for sorting and pathfinding algorithms.