Algorithm Guidecomplexity: O(n)

Tree Traversal

Ways to visit every node of a tree exactly once. Depending on when you visit, it splits into preorder (root first), inorder (left → root → right, sorted order in a BST), postorder (root last), and level order.

01Tree Traversal

Explore How It Works

Start an inorder traversal. Visit left subtree → root → right subtree — in a BST this prints in sorted order.

From root 50 go left, then left of 30 — reach the leftmost node 20. Print 20 first.

20 has no left child, so print its parent 30. Output: 20 · 30

Print 30's right child 40. Output: 20 · 30 · 40

The left subtree is done. Now print the root 50. Output: …40 · 50

Move to the right subtree and print 70's left child 60. Output: …50 · 60

Print 60's parent 70. Output: …60 · 70

Finally print 70's right child 80. Output: …70 · 80

Inorder traversal complete · 20 30 40 50 60 70 80. An inorder walk of a BST always yields ascending sorted order.

Live Python

1def inorder(node):

2 if not node:

3 return

# left first

4 inorder(node.left)

5 visit(node) # left → root → right

6 inorder(node.right)

1 / 9

02 Understand It Simply

For Everyone

🔑How It Works

Pre-, in- and post-order differ only in when the root is visited. On a binary search tree, in-order visits the values in ascending order.

💡In Plain Words

Ways to stop by every node of a tree once.

When you visit the root determines preorder, inorder, or postorder — and an inorder walk of a BST yields sorted order.

📍Where It's Used

–Printing an entire folder
–evaluating expressions (parse trees)
–serializing trees

03 Python Implementation

A clean, readable reference implementation of the core logic of Tree Traversal.

core_implementation.py

def inorder(node):
    if not node:
        return
    inorder(node.left)
    visit(node)          # left → root → right
    inorder(node.right)

def preorder(node):
    if not node:
        return
    visit(node)          # root first
    preorder(node.left)
    preorder(node.right)

def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    visit(node)          # root last

04 Frequently Asked Questions

FAQ

What is Tree Traversal?+

What is the time complexity of Tree Traversal?+

The time complexity of Tree Traversal is O(n). Follow the step-by-step visualization to see exactly why.

Where is Tree Traversal used?+

Printing an entire folder, evaluating expressions (parse trees), serializing trees.

What's a simple analogy for Tree Traversal?+

Pre-, in- and post-order differ only in when the root is visited. On a binary search tree, in-order visits the values in ascending order.

→ Trees — see allRelated

🌳AVL Tree

O(log n)

🌳Segment Tree

Query/Update O(log n)

🌳Trie

O(m) (string length)