Binary Tree Traversal Visualizer
Build a binary search tree and watch four traversal algorithms visit each node step by step. Nodes highlight in the correct order with numbered badges showing the visit sequence.
Controls
Results
Reference Guide
Tree Traversals
A tree traversal visits every node exactly once in a specific order. The four standard methods differ in when they visit the current node relative to its subtrees. Depth-first traversals (inorder, preorder, postorder) use a stack, while level-order traversal uses a queue.
For a binary search tree, inorder traversal always produces values in sorted (ascending) order. This property makes BSTs useful for sorted data retrieval.
Inorder vs Preorder vs Postorder
Inorder (LNR) visits the left subtree, then the node, then the right subtree. For BSTs this gives sorted output.
Preorder (NLR) visits the node first, then left, then right. Useful for creating a copy of the tree or serializing its structure.
Postorder (LRN) visits both subtrees before the node. Useful for safely deleting a tree or evaluating expression trees from the bottom up.
Level-Order (BFS)
Level-order traversal visits nodes level by level from top to bottom, left to right. It uses a queue data structure instead of recursion.
This is a breadth-first search (BFS) approach. It is useful for finding the shortest path in unweighted trees, printing the tree level by level, and checking completeness.
Binary Search Trees
A binary search tree (BST) maintains the invariant that for every node, all values in the left subtree are smaller and all values in the right subtree are greater or equal.
BST operations (insert, search, delete) take O(h) time where h is the tree height. A balanced BST has h = O(log n), but a skewed tree degrades to h = O(n), behaving like a linked list.