SimuVedaAlgorithms Lab Open in the lab

Trees / Beginner

Inorder Traversal Visualizer

Left subtree, then the node, then the right subtree.

Start the Inorder Traversal simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(h)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Inorder traversal: left subtree, right subtree and the node itself, in the order shown in the code.
  2. At node 50.
  3. Go left from 50.
  4. At node 30.
  5. Go left from 30.
  6. At node 20.
  7. Visit 20.
  8. Back at 30.
  9. Visit 30.
  10. Go right from 30.
  11. At node 40.
  12. Go left from 40.
  13. At node 35.
  14. Visit 35.
  15. Back at 40.
  16. Visit 40.
  17. Back at 30.
  18. Back at 50.
  19. Visit 50.
  20. Go right from 50.
  21. … 12 more steps …
  22. Visit 80.
  23. Back at 70.
  24. Back at 50.
  25. Done. Visit order: 20, 30, 35, 40, 50, 60, 65, 70, 80.

Try it with your own input →

Inorder traversal in Java, Python, C++, C and JavaScript

void inorder(Node n) {
  if (n == null) return;
  inorder(n.left);
  visit(n);
  inorder(n.right);
}
def inorder(n):
    if n is None:
        return
    inorder(n.left)
    visit(n)
    inorder(n.right)
void inorder(Node* n) {
  if (!n) return;
  inorder(n->left);
  visit(n);
  inorder(n->right);
}
void inorder(struct Node* n) {
  if (n == NULL) return;
  inorder(n->left);
  visit(n);
  inorder(n->right);
}
function inorder(n) {
  if (n === null) return;
  inorder(n.left);
  visit(n);
  inorder(n.right);
}

In an interview

Inorder on a BST gives the values in sorted order. That is the quickest way to "validate a BST".

More trees