Learn C++ in step-by-step lessons.
A binary search tree is an ordered list, that starts at the root. Each node of the tree can have a left and right sub-tree.
When we insert into a tree, we start at the root. If the root is empty the new node goes there. If not, if the new value is less than the root, we insert into the left sub-tree, otherwise we insert into the right subtree.
To search, we start at the root and then search either the left or right sub-tree until the node is empty or the search term is found.
To traverse the tree and print in order we start at the root. We traverse its left sub-tree, then print it, then traverse the right sub-tree.
Each node of a tree has the value and a pointer to the left and right subtrees. These values are initially set to null.
Operations on a tree are often done recursively.
In the demo program (because Javascript doesn't have pointers) the tree root is at tree[1]: left is n*2, right is n*2+1. In order to animate the operations, a stack is used in place of recursion.
Binary Search Trees