tree traversal

Tree traversal is the process of visiting every node of a tree data structure exactly once, in a systematic order, to read, update, or check each value.

A linked list has one natural order, from first element to last. A tree branches, so a traversal must decide which child to visit next and when to return to a parent. Traversals fall into two families. Depth-first traversals follow one branch down to a leaf, a node with no children, before backtracking, while breadth-first traversals sweep the tree one level at a time.

On a binary tree, four standard orders fall out of those two families:

  • Preorder: Visit the node, then its left subtree, then its right subtree. This order suits copying a tree or writing an expression in prefix notation.
  • Inorder: Visit the left subtree, then the node, then the right subtree. On a binary search tree, this order yields the keys in sorted order.
  • Postorder: Visit the left subtree, then the right subtree, then the node. Children finish before their parent, which suits freeing a tree or evaluating an expression tree.
  • Level order: Visit the nodes one depth at a time, left to right. A queue holds the nodes waiting their turn, as in breadth-first search.

Pick one of these orders below and step through its visit sequence on a small binary search tree:

Interactive diagram — enable JavaScript to view.

The three depth-first orders map naturally onto recursion, because each subtree is itself a smaller tree. An explicit stack produces the same order without deep call chains. Every traversal touches each of the n nodes once, so it runs in O(n) time. Depth-first orders need extra space proportional to the tree’s height, while level order needs space proportional to its widest level.

Preorder and postorder extend to trees whose nodes have any number of children, but inorder needs the single split point that a binary node provides. File system tools walk nested directories as trees, and compilers and linters walk abstract syntax trees, which Python exposes through its ast module.

Python Stacks, Queues, and Priority Queues in Practice

Tutorial

Python Stacks, Queues, and Priority Queues in Practice

In this tutorial, you'll take a deep dive into the theory and practice of queues in programming. Along the way, you'll get to know the different types of queues, implement them, and then learn about the higher-level queues in Python's standard library. Be prepared to do a lot of coding.

intermediate algorithms data-structures

For additional information on related topics, take a look at the following resources:

Have a question about this? Mentor AI can show you examples, compare related terms, and point you to tutorials.

  • Ask Mentor AI
  • Pick a question and Mentor AI takes it from here.
By Martin Breuss • Updated Oct. 25, 2026
Computer Science Glossary Share Feedback