juniorTrees

What are the different types of tree traversals? Name them.

Updated Apr 28, 2026

Short answer

Tree traversals are ways of visiting every node in a tree exactly once in a specific order. The main types are Depth-First Traversals — Preorder, Inorder, and Postorder — and Breadth-First Traversal — Level Order Traversal. The choice of traversal depends on the problem, such as searching, sorting, or processing hierarchical data.

Deep explanation

A tree traversal is a process of systematically visiting all nodes in a tree. Unlike linear data structures such as arrays or linked lists, trees can be explored in multiple valid orders because each node may have multiple children.

The main types of tree traversals are:

1. Depth-First Traversal (DFS)

Depth-first traversal explores as far down a branch as possible before moving to another branch. It is commonly implemented using recursion or a stack.

The three DFS variations are determined by when the current node is processed relative to its children.

Preorder Traversal

Order: Root → Left → Right

In preorder traversal, the node is processed before visiting its child subtrees.

Example:

TypeScript
A
       / \
      B   C
     / \
    D   E

Preorder result:

TypeScript
A B D E C

Common uses:

  • Creating a copy of a tree
  • Serializing a tree structure
  • Processing parent nodes before children

Inorder Traversal

Order: Left → Root → Right

In inorder traversal, the left subtree is visited first, then the current node, then the right subtree.

Example:

TypeScript
A
       / \
      B   C
     / \
    D   E

Inorder result:

TypeScript
D B E A C

A key property:

  • In a Binary Search Tree (BST), inorder traversal visits nodes in sorted ascending order.

Postorder Traversal

Order: Left → Right → Root

In postorder traversal, child nodes are processed before the parent node.

Example:

TypeScript
A
       / \
      B   C
     / \
    D   E

Postorder result:

TypeScript
D E B C A

Common uses:

  • Deleting a tree safely
  • Evaluating expression trees
  • Processing dependencies where children must finish first

2. Breadth-First Traversal (BFS)

Breadth-first traversal visits nodes level by level, starting from the root. It is also called Level Order Traversal.

It typically uses a queue.

Example:

TypeScript
A
       / \
      B   C
     / \
    D   E

Level order result:

TypeScript
A B C D E

Common uses:

  • Finding the shortest path in an unweighted tree
  • Processing data by hierarchy level
  • Printing tree structures visually

Recursive DFS Example

Python
def preorder(node):
    if node is None:
        return


    print(node.value)
    preorder(node.left)
    preorder(node.right)

The recursive approach uses the call stack to remember which nodes still need to be visited.

Iterative BFS Example

Python
from collections import deque


def level_order(root):
    if root is None:
        return


    queue = deque([root])


    while queue:
        node = queue.popleft()
        print(node.value)


        if node.left:
            queue.append(node.left)


        if node.right:
            queue.append(node.right)

Time and Space Complexity

For all standard tree traversals:

  • Time Complexity: O(n) because every node is visited once.
  • Space Complexity:
  • DFS recursion: O(h), where h is the height of the tree.
  • BFS queue: O(w), where w is the maximum width of the tree.

The best traversal depends on the required output and the structure of the tree.

Real-world example

A company file system can be represented as a tree:

TypeScript
Company
├── Engineering
│   ├── Backend
│   └── Frontend
└── Sales

Different traversals solve different problems:

  • Preorder: Show folders before their contents, useful for displaying a directory structure.
  • Inorder: Useful mainly for binary search trees where sorted ordering is needed.
  • Postorder: Delete all files inside folders before deleting the folders themselves.
  • Level Order: Display the organisation hierarchy one management level at a time.

Example: deleting a folder structure safely:

Python
def delete_folder(node):
    if node is None:
        return


    delete_folder(node.left)
    delete_folder(node.right)


    print("Deleting:", node.name)

This uses postorder traversal because child folders must be removed before the parent folder.

Common mistakes

  • * Confusing inorder traversal with a traversal that works for all trees
  • sorted output is only guaranteed for Binary Search Trees.
  • * Forgetting that preorder, inorder, and postorder are depth-first traversals, not separate tree types.
  • * Using BFS without understanding that it requires extra memory for the queue.
  • * Assuming recursive DFS always uses constant memory
  • it uses the call stack based on tree height.
  • * Mixing up the order of node processing in preorder and postorder traversals.
  • * Forgetting to handle the empty tree case where the root is `null` or `None`.

Follow-up questions

  • What is the difference between DFS and BFS tree traversal?
  • Why does inorder traversal of a Binary Search Tree produce sorted values?
  • How would you implement a preorder traversal without recursion?
  • When would you choose level order traversal over depth-first traversal?
  • What is the space complexity of a recursive tree traversal?

More Trees interview questions

View all →