Draw the binary search tree or binary heap built by inserting values one at a time. For a binary search tree, it shows the traversal orders (preorder, inorder and postorder), the path of nodes compared when searching for a value, and the shape after a node is deleted. For a heap, you can check which value goes into which array position and how the values are arranged after the root is removed.
Favorites and recently used calculators are stored only in this browser (localStorage).
Tree shape
Preorder
–
Inorder
–
Postorder
–
Level order (breadth-first, top level first)
–
Height (number of levels)
–
Number of nodes
–
Nodes compared during the search
–
Array layout ([index] value)
–
Removed values
–
The height is counted so that a tree consisting only of the root has height 1 (some texts count the root as 0). The small number at the top right of each node in the heap diagram is its array index, with the root at index 0: the children of index i are at 2i+1 and 2i+2, and its parent is at (i−1)÷2 rounded down.
See it as a graph
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
What is a binary search tree?
A binary search tree is a binary tree in which, for every node, all values in the left subtree are smaller than the node and all values in the right subtree are larger. A search starts at the root and goes left if the value sought is smaller and right if it is larger, so the number of comparisons is at most the height of the tree. Insertion follows the same path and attaches the new node where the path ends. The example “50 30 70 20 40 60 80” gives a tree of height 3, and 60 is found after three comparisons, with 50, 70 and 60.
Traversal orders (preorder, inorder and postorder)
There are several orders for visiting every node of a tree: preorder visits the node first and then traverses the left and right subtrees; inorder visits the left subtree, then the node, then the right subtree; and postorder traverses the left and right subtrees before visiting the node. An inorder traversal of a binary search tree lists the values in ascending order. Postorder processes subtrees first, so it is used to delete a tree or to evaluate an expression tree (Reverse Polish notation), while preorder is used, for example, to copy a tree. Visiting the nodes level by level from the top is level order (breadth-first) traversal.
Deletion and imbalance
To delete a node from a binary search tree, a node with no children is simply removed, and a node with one child is replaced by that child. For a node with two children, the smallest value in its right subtree (or the largest in its left subtree) is moved into its position, and the node it came from is deleted. If sorted values are inserted in order, the tree grows in only one direction and becomes like a linked list, so a search can take up to n comparisons. To prevent this, self-balancing binary search trees such as AVL trees and red-black trees, which reshape themselves on every insertion and deletion, are used.
Heaps and their array representation
A heap is a binary tree in which each parent's value is greater than or equal to its children's (a max-heap) or less than or equal to them (a min-heap), and it has the shape of a complete binary tree, with nodes filled level by level from the left. If the nodes are stored in an array level by level with the root at index 0, the children of node i are at indexes 2i+1 and 2i+2, so no pointers are needed. To insert a value, place it at the end and move it up while comparing it with its parent; to remove the root, move the last value to the root and move it down while comparing it with its children. Both take O(log n) work, proportional to the height of the tree, which is why heaps are used for priority queues and heapsort.
With the root at a[0], the children of a[i] are a[2i+1] and a[2i+2], and its parent is a[(i−1) ÷ 2, rounded down]. For i = 4, the children are a[9] and a[10] and the parent is a[(4−1) ÷ 2] = a[1]. With the root at a[1], the children are a[2i] and a[2i+1] and the parent is a[i ÷ 2], so it is important to check which convention is being used. Because a heap is a complete binary tree, it can be stored in an array without pointers, and parents and children are found by index arithmetic alone.
45 is placed at a[6], whose parent is a[(6−1) ÷ 2] = a[2] = 40. Since 45 > 40, they are swapped and 45 moves to a[2]. Its next parent, a[0] = 50, is larger than 45, so the process stops, giving 50, 30, 45, 10, 20, 35, 40. Swaps happen at most as many times as the height of the tree, so insertion takes O(log n), and removing the maximum is also O(log n). For this reason, binary heaps are commonly used to implement priority queues.
CIn order of closeness to the root (shallowest first)
Show answer and explanation
Answer: A. In ascending order (smallest first)
In a binary search tree, for every node, all values in the left subtree are smaller than the node and all values in the right subtree are larger. Visiting the left subtree, the node and then the right subtree therefore visits the values from smallest to largest, so the result is in ascending order. Visiting nodes in order of closeness to the root is a breadth-first (level-order) traversal, which goes level by level from left to right. The insertion order affects the shape of the tree but does not match the order of any of these traversals.
The root is 50; its left child is 30 (with children 20 and 40) and its right child is 70 (with children 60 and 80). Post-order visits the left subtree as 20, 40, 30 and the right subtree as 60, 80, 70, and only then the root 50. 50, 30, 20, 40, 70, 60, 80 is the pre-order result, which visits each node first, and 20, 30, 40, … is the in-order result. Post-order is used when children must be processed first, such as when deleting a tree or producing postfix notation from an expression tree.
When values are inserted in ascending order, each new value becomes the right child of the previous maximum, so the tree becomes a single chain extending only to the right (height 999). 1000 is at the very bottom, so it is compared with all 1,000 nodes, 1, 2, …, 1000, which is O(n), the same as walking a linked list from the front. A balanced tree would have only about log₂ 1000 ≈ 10 levels, so using a self-balancing binary search tree such as an AVL tree or a red-black tree, which reshapes itself on every insertion and deletion, keeps the worst case at O(log n).
FAQ
What is the difference between a binary search tree and a heap?
In a binary search tree the order between the left and right subtrees is fixed, which makes it suited to searching for any value. In a heap only the order between a parent and its children is fixed, which makes it suited to taking out the maximum (or minimum) value quickly. To find an arbitrary value in a heap, you have to examine the whole heap.
Why does an inorder traversal list the values in ascending order?
Inorder traversal visits a node's left subtree (all values smaller than the node) before the node and its right subtree (all larger values) after it. Because this holds at every node, the whole sequence is in ascending order.
How is the height counted?
This tool counts the number of levels, so a tree consisting only of the root has height 1. If the height is counted as the number of edges from the root to the deepest leaf, a tree consisting only of the root has height 0. Exam questions state which convention they use.
How does this come up in exams?
IT certification exams such as Japan's Fundamental Information Technology Engineer Examination often ask about the shape and traversal orders of a binary search tree built by inserting values in order, the index relationships when a heap is stored in an array, and the array order after a value is added. Choose an example and compare the diagram and array layout with your own answer.