My IT Utilities

Binary tree traversals

Generate a binary search tree and step through preorder, inorder or postorder traversals with a recursive C++ function.

Everything is simulated in this browser; nothing is sent to any server.

Visits the node, then the left subtree and then the right one.

The function is called with node 60

The function is called with node 60

Binary tree

60458568215532

Output

No node has been visited yet

  • Not visited
  • Running
  • On the stack
  • Visited

Step 1 / 44

Code

#include <iostream>
using namespace std;
class Node { // A node holds its value and pointers to its two children
private: // Private attributes: only the methods touch them
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
void preorder(Node* node) { // Traverses the subtree rooted at node
if (node == nullptr) return; // Base case: an empty subtree has nothing to visit
cout << node->getValue() << " "; // Visits the node: processes its value
preorder(node->getLeft()); // Traverses the left subtree
preorder(node->getRight()); // Traverses the right subtree
} // Returns to the caller
Node* insert(Node* root, int v) { // Inserts v into the search tree and returns the root
if (root == nullptr) return new Node(v); // Empty spot: the new node goes here
if (v < root->getValue()) // Smaller values go left and larger ones go right
root->setLeft(insert(root->getLeft(), v));
else
root->setRight(insert(root->getRight(), v));
return root;
}
Node* buildTree() { // Builds the tree by inserting the values one by one
int values[] = {60, 45, 85, 68, 21, 55, 32}; // The values of the tree shown, in insertion order
Node* root = nullptr;
for (int v : values) root = insert(root, v);
return root;
}
int main() {
Node* root = buildTree(); // The tree from the animation, already built
preorder(root); // First call, from main
cout << endl; // End of the traversal
return 0;
}

This tool generates a binary search tree (BST) with random values and traverses it step by step with a recursive C++ function. You pick preorder, inorder or postorder and see on the same tree when each node is visited: before its children, between them or after them. Nodes are colored by state (not visited, running, on the stack or visited), an output strip shows the values in visiting order and the code highlights the line being executed. Calls with nullptr are shown too, the base case that stops the recursion. You can change the size from 3 to 15 nodes and generate another tree. Everything is simulated in your browser.

How to use it

  1. Pick the traversal: Preorder, Inorder or Postorder.
  2. Adjust the tree size with the slider or press Generate new tree; the animation goes back to the first step.
  3. Press Play or move with the previous and next step buttons, and change the speed if you need to.
  4. Watch the colored nodes, the output strip with the visited values and the highlighted line of C++ code.

Frequently asked questions

What is a binary tree and what is a binary search tree?
A binary tree is a structure where each node has at most two children, left and right. In a binary search tree (BST) the values in the left subtree are also smaller than the node and the ones in the right subtree are larger.
What is the difference between preorder, inorder and postorder?
What changes is when the node is visited relative to its children. In preorder the node is visited first and then the left and right subtrees; in inorder, the left subtree, the node and the right subtree; in postorder, the left subtree, the right subtree and the node last. Preorder is used to copy a tree, inorder to read a BST in order and postorder to free or evaluate a tree, because children are processed before their parent.
Why does the inorder traversal of a BST come out sorted?
Because in a BST everything to the left of a node is smaller and everything to the right is larger. Visiting the left subtree, then the node and then the right subtree produces the values from smallest to largest.
How do you implement a recursive traversal in C++?
With a function that takes a pointer to a node. If the pointer is nullptr it returns without doing anything: that is the base case. Otherwise it visits the node and calls itself with the left child and the right child, in the order the traversal requires.

Related tools