Binary search tree visualiser

Type the values in the order they are inserted and pick what to watch: the tree being built one value at a time (each value is compared with the nodes on its way down), a search for a value, or an inorder, preorder or postorder traversal with the recursive calls piling up on the call stack and the output growing.

How to use it

1Type the values in the order they are inserted, pick what to watch (insert, search or a traversal), or tap an example.
2Press Show me, then Play. Use Back and Next, the slider or the arrow keys to go at your own speed.
3Watch each value walk down the tree, or the traversal's recursive calls pile up, with the Java line that is running.

Not sure what to type? Tap an example:

build a tree from 50, 30, 70, 20, 40, 60, 80 a lopsided tree: 10, 20, 30, 40 search for 60: found search for 55: not there inorder: the values come out sorted preorder: the root comes first postorder: the root comes last a repeated value is not inserted again

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

Result

Result: inorder: 20 30 40 50 60 70 80

Every step in words (45 steps)

inorder(root) is called with the root, 50.
t is 50, not null, so: left subtree, then the node, then right subtree.
Go left: inorder(t.left) is called, and t.left is 30.
t is 30, not null, so: left subtree, then the node, then right subtree.
Go left: inorder(t.left) is called, and t.left is 20.
t is 20, not null, so: left subtree, then the node, then right subtree.
Go left: inorder(t.left) is called, and t.left is null.
t is null, so there is nothing to do: the call returns at once.
Print 20.
Go right: inorder(t.right) is called, and t.right is null.
t is null, so there is nothing to do: the call returns at once.
inorder(20) has done all three parts, so it returns.
Print 30.
Go right: inorder(t.right) is called, and t.right is 40.
t is 40, not null, so: left subtree, then the node, then right subtree.
Go left: inorder(t.left) is called, and t.left is null.
t is null, so there is nothing to do: the call returns at once.
Print 40.
Go right: inorder(t.right) is called, and t.right is null.
t is null, so there is nothing to do: the call returns at once.
inorder(40) has done all three parts, so it returns.
inorder(30) has done all three parts, so it returns.
Print 50.
Go right: inorder(t.right) is called, and t.right is 70.
t is 70, not null, so: left subtree, then the node, then right subtree.
Go left: inorder(t.left) is called, and t.left is 60.
t is 60, not null, so: left subtree, then the node, then right subtree.
Go left: inorder(t.left) is called, and t.left is null.
t is null, so there is nothing to do: the call returns at once.
Print 60.
Go right: inorder(t.right) is called, and t.right is null.
t is null, so there is nothing to do: the call returns at once.
inorder(60) has done all three parts, so it returns.
Print 70.
Go right: inorder(t.right) is called, and t.right is 80.
t is 80, not null, so: left subtree, then the node, then right subtree.
Go left: inorder(t.left) is called, and t.left is null.
t is null, so there is nothing to do: the call returns at once.
Print 80.
Go right: inorder(t.right) is called, and t.right is null.
t is null, so there is nothing to do: the call returns at once.
inorder(80) has done all three parts, so it returns.
inorder(70) has done all three parts, so it returns.
inorder(50) has done all three parts, so it returns.
Done. The inorder traversal is 20 30 40 50 60 70 80.

Start again

About the Binary search tree visualiser

What it does

Builds a binary search tree from your values, one at a time, and shows what the recursive insert method does: each value is compared with the node it meets, goes left if it is smaller and right if it is larger, and becomes a new node where there is nothing in the way. You can also search for a value, or watch an inorder, preorder or postorder traversal, with the calls on the call stack, the node being worked on, and the output so far.

The rules it follows

Binary search tree: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger.
Repeated values: a value that is already in the tree is not inserted again.
Inorder: left subtree, node, right subtree (a binary search tree comes out in ascending order). Preorder: node, left, right. Postorder: left, right, node.
Null calls: a call on a missing child (null) returns at once; the call stack shows them too.

The limits

1 to 12 whole numbers, each from -99 to 999, so the tree always fits on the page. To draw a tree from its traversals instead, use the binary tree tool.

Common questions

What is the inorder traversal of a binary search tree?

It visits the left subtree, then the node, then the right subtree, so the values come out in ascending order. For the tree built from 50, 30, 70, 20, 40, 60, 80 it is 20 30 40 50 60 70 80.

How do you insert a value into a binary search tree?

Start at the root. If the value is smaller than the node go left, if it is larger go right, and repeat until you reach an empty place (null): the new node goes there. A value that is already in the tree is left out.

What is the difference between preorder, inorder and postorder?

They differ only in when the node itself is visited: before its subtrees (preorder), between them (inorder) or after them (postorder). The left subtree is always visited before the right one.

Why does the tree look lopsided when the values are already sorted?

Each new value is larger than everything before it, so it always goes right and the tree becomes a chain. Try 10, 20, 30, 40 to see it.

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 →