Prashnikaप्रश्निका
Code
About

Binary tree traversal visualiser

Build any binary tree by typing its root and then the children of each node: two boxes appear under every node you fill in. Pick preorder, inorder or postorder and press Play: the recursive calls pile up on the call stack, the node being visited lights up and the output grows, with the Java line that is running lit.

How to use it

  1. 1Type the root, then fill in the boxes that appear under each node (leave the ones the tree does not have empty), or tap an example.
  2. 2Pick preorder, inorder or postorder, press Play, then use Back and Next, the slider or the arrow keys to go at your own speed.
  3. 3Watch the recursive calls pile up on the call stack, the node being visited light up and the output grow, with the Java line that is running.
Not sure what to type? Tap an example:
preorder of a six-node treeinorder of the same treepostorder of the same treean expression tree: inorder gives A*B+C/Dthe same expression tree in postorder: A B * C D / +a tree that only goes lefta binary search tree of numbers: inorder is sorted
How to walk it

The animation needs JavaScript. Every step is written out below.

Result

Result
preorder: P Q R S
Every step in words (27 steps)
  1. preorder(root) is called with the root, P.
  2. t is P, not null, so: the node, then left subtree, then right subtree.
  3. Print P.
  4. Go left: preorder(t.left) is called, and t.left is Q.
  5. t is Q, not null, so: the node, then left subtree, then right subtree.
  6. Print Q.
  7. Go left: preorder(t.left) is called, and t.left is R.
  8. t is R, not null, so: the node, then left subtree, then right subtree.
  9. Print R.
  10. Go left: preorder(t.left) is called, and t.left is S.
  11. t is S, not null, so: the node, then left subtree, then right subtree.
  12. Print S.
  13. Go left: preorder(t.left) is called, and t.left is null.
  14. t is null, so there is nothing to do: the call returns at once.
  15. Go right: preorder(t.right) is called, and t.right is null.
  16. t is null, so there is nothing to do: the call returns at once.
  17. preorder(S) has done all three parts, so it returns.
  18. Go right: preorder(t.right) is called, and t.right is null.
  19. t is null, so there is nothing to do: the call returns at once.
  20. preorder(R) has done all three parts, so it returns.
  21. Go right: preorder(t.right) is called, and t.right is null.
  22. t is null, so there is nothing to do: the call returns at once.
  23. preorder(Q) has done all three parts, so it returns.
  24. Go right: preorder(t.right) is called, and t.right is null.
  25. t is null, so there is nothing to do: the call returns at once.
  26. preorder(P) has done all three parts, so it returns.
  27. Done. The preorder traversal is P Q R S.
Start again

About the Binary tree traversal visualiser

What it does

Walks a binary tree that you build yourself and shows what the recursive traversal method does at every call: it is called on a node, calls itself on the left and right children (a missing child is a call on null that returns at once) and visits the node at the moment its order says. The call stack, the node being worked on and the output so far are shown at every step.

The three orders

  • Preorder: node, left subtree, right subtree.
  • Inorder: left subtree, node, right subtree.
  • Postorder: left subtree, right subtree, node.

For an expression tree (operators in the inner nodes, operands in the leaves) preorder gives the prefix form, inorder the infix form without brackets and postorder the postfix form.

The limits

Up to 15 nodes, each with its own value of up to 6 characters (so the picture can show which node was printed). To get the height, leaves and every node's parent and sibling, or to rebuild a tree from two traversals, use the binary tree tool.

Common questions

What is the preorder traversal of a binary tree?

Visit the node first, then the whole left subtree, then the whole right subtree. For the tree A, B, C, D, -, E, F (A with children B and C; B with the left child D; C with children E and F) it is A B D C E F.

How do the three traversals give prefix, infix and postfix?

In an expression tree the operators are the inner nodes. Preorder prints each operator before its operands (prefix), inorder between them (infix) and postorder after them (postfix).

Why must every node have a different value?

The picture marks a node as printed by its value, so two nodes with the same value could not be told apart. Give each node its own letter or number.

Can I see the code in Python, JavaScript or C++?

Yes. Choose the language in the menu above the code. Only the listing changes: the steps are always worked out from the Java program that ISC uses, and the highlighted line moves to the matching line of the language you chose.

Practise on real ISC questions

More Computer Science tools

All study tools →