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

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

  1. 1Type the values in the order they are inserted, pick what to watch (insert, search or a traversal), or tap an example.
  2. 2Press Show me, then Play. Use Back and Next, the slider or the arrow keys to go at your own speed.
  3. 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, 80a lopsided tree: 10, 20, 30, 40search for 60: foundsearch for 55: not thereinorder: the values come out sortedpreorder: the root comes firstpostorder: the root comes lasta repeated value is not inserted again
What to watch

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

Result

Result
inorder 20 30 40 50 60 70 80; height 3
Every step in words (38 steps)
  1. Insert 50: insert(root, 50) is called.
  2. root is null: there is no node here, so 50 goes here.
  3. return new Node(50): the new node is made and the call returns it.
  4. The calls return, each linking its child to the node above. 50 is now in the tree.
  5. Insert 30: insert(root, 30) is called.
  6. 30 < 50 is true, so go left: insert(root.left, 30) is called, and root.left is null.
  7. root is null: there is no node here, so 30 goes here.
  8. return new Node(30): the new node is made and the call returns it.
  9. The calls return, each linking its child to the node above. 30 is now in the tree.
  10. Insert 70: insert(root, 70) is called.
  11. 70 < 50 is false and 70 > 50 is true, so go right: insert(root.right, 70) is called, and root.right is null.
  12. root is null: there is no node here, so 70 goes here.
  13. return new Node(70): the new node is made and the call returns it.
  14. The calls return, each linking its child to the node above. 70 is now in the tree.
  15. Insert 20: insert(root, 20) is called.
  16. 20 < 50 is true, so go left: insert(root.left, 20) is called, and root.left is 30.
  17. 20 < 30 is true, so go left: insert(root.left, 20) is called, and root.left is null.
  18. root is null: there is no node here, so 20 goes here.
  19. return new Node(20): the new node is made and the call returns it.
  20. The calls return, each linking its child to the node above. 20 is now in the tree.
  21. Insert 40: insert(root, 40) is called.
  22. 40 < 50 is true, so go left: insert(root.left, 40) is called, and root.left is 30.
  23. 40 < 30 is false and 40 > 30 is true, so go right: insert(root.right, 40) is called, and root.right is null.
  24. root is null: there is no node here, so 40 goes here.
  25. return new Node(40): the new node is made and the call returns it.
  26. The calls return, each linking its child to the node above. 40 is now in the tree.
  27. Insert 60: insert(root, 60) is called.
  28. 60 < 50 is false and 60 > 50 is true, so go right: insert(root.right, 60) is called, and root.right is 70.
  29. 60 < 70 is true, so go left: insert(root.left, 60) is called, and root.left is null.
  30. root is null: there is no node here, so 60 goes here.
  31. return new Node(60): the new node is made and the call returns it.
  32. The calls return, each linking its child to the node above. 60 is now in the tree.
  33. Insert 80: insert(root, 80) is called.
  34. 80 < 50 is false and 80 > 50 is true, so go right: insert(root.right, 80) is called, and root.right is 70.
  35. 80 < 70 is false and 80 > 70 is true, so go right: insert(root.right, 80) is called, and root.right is null.
  36. root is null: there is no node here, so 80 goes here.
  37. return new Node(80): the new node is made and the call returns it.
  38. The calls return, each linking its child to the node above. 80 is now in the tree.

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 →