Introduction

A linked list makes it easier to store a variable amount of data.  However, since access is only available at the head and current nodes, they can be difficult to search/access.  Binary trees offer an advantage -- by using two pointers instead of one, it is now possible to use binary search instead of linear search.  Unfortunately, it also becomes more difficult to do linear search in that a tree traversal is now required.
 

Resources

• For starters, this example will let you insert, delete, and search for nodes in a binary search tree.  Notice that for each node, all nodes to the left have smaller values and all nodes to the right have larger values.  Try to observe which nodes get visited during each operation.
• You might now want to see a faster demo of a binary search tree.  Note: the letter in each node represents its key, and the number in each node represents the order that it was inserted in.  In a binary search tree, new nodes are always inserted as leaves onto the existing tree.
• In the previous examples, you can see how the "up-down" organization of binary search tree makes it easy to find and insert values.  However, just like you can't follow a pointer "backwards" on a singly linked list, you can't follow a pointer "up" on a binary tree.  To see how traversals (to visit every node) work, try this example.  Click on "Traversals" in the top left, and then click on "Start Visualization" at the bottom right.  You should definitely try pre-order, in-order, and post-order traversals, but level-order might now make sense until you've learned about stacks and queues.