Previous | Table of Contents | Next

{ Introduction to Binary Search Trees. }

Objectives

By the end of this chapter, you should be able to:

  • Define tree data structures and real world use cases
  • Compare and contrast trees, binary trees, and binary search trees
  • Implement tree and node data structures, along with methods for inserting and finding nodes

So far we have learned about arrays, linked lists, stacks, and queues. And while these are all very helpful data structures, there is another kind of data structure which allows for a faster lookup if ordered properly.

This data structure is used quite frequently to organize and is called a tree. Trees, like many of the other data structures we've seen so far, consist of collections of nodes. Unlike things like linked lists, however, nodes in a tree are organized in parent-child relationships.

If you've written JavaScript code to run in the browser, you've likely seen an example of a tree before. In fact, the DOM has a tree structure! For example, consider this HTML:

<html lang="en">
    <head>
      <meta charset="UTF-8">
      <title>some html</title>
    </head>
    <body>
        <h1>Title</h1>
        <div>A div</div>
        <div>Another div</div>
    </body>
</html>

This HTML page can be represented as a tree. The html element represents the top node in the tree, and has two children head and body. Similarly, the head element has two children, while the body element has three:

Tree Terminology

There are a number of common terms you'll hear or read when you're learning about trees. Here are a few:

Root - The top node in a tree.
Child -A node directly connected to another node when moving away from the Root.
Parent - The converse notion of a child.
Siblings -A group of nodes with the same parent.
Descendant - A node reachable by repeated proceeding from parent to child.
Ancestor - A node reachable by repeated proceeding from child to parent.
Leaf - A node with no children.
Edge - The connection between one node and another.
Path -A sequence of nodes and edges connecting a node with a descendant.
Level - The level of a node is defined by 1 + (the number of connections between the node and the root).
Height of node - The height of a node is the number of edges on the longest path between that node and a descendant leaf.
Height of tree- The height of a tree is the height of its root node.
Depth - The depth of a node is the number of edges from the tree's root node to the node.

There are many different kinds of trees used for many different purposes including database indexing, structuring systems (like your file system) and many more.

Binary Search Trees

One type of tree is called a Binary Tree. This is a tree in which each node has at most two children. Among binary trees, the specific kind of tree that we will be looking at now is a Binary Search Tree. A binary search tree is a special kind of tree where each node is in a sorted order: all nodes to the left of a given node must have values less than the given node's value, and all nodes to the right of a given node must have values greater than the given node's value. Let's see what a BST looks like:

Notice that in the above example, every node to the left of the root has a value less than 8; every node to the right of the root has a value greater than 8. Similarly, every node to the left of the 3 node has a value less than 3, while every node to the right of the 3 node has a value greater than 3.

Inserting a node in a binary tree

One of the first methods to implement with a binary tree is inserting a node. The algorithm goes as follows (and can be done iteratively and recursively)

  • Start at the root
  • If there is nothing there, insert that node
  • If the value of the node you are inserting for is less than the root go to the left node (if it exists)
  • If the value of the node you are inserting for is greater than the root go to the right node (if it exists)
  • Keep moving right or left until you find a node with no left or right value. Once you find that empty value, place the newly created node there.

Finding a node in a binary tree

Now that we can insert nodes into a tree, we need to think about how to find them. The algorithm goes as follows (and can be done iteratively and recursively)

  • Start searching at the root
  • If the value you are looking for is less than the root go to the left node (if it exists)
  • If the value you are looking for is greater than the root go to the right node (if it exists)
  • Keep moving right or left until you find the node with that value, otherwise return undefined.

Performance

Binary search trees have impressive performance characteristics since all operations can be done in O(log(n)) time on average. However, this is not always the case if a tree is unbalanced (more nodes on one side than another). The worst case runtime for a BST can be O(n) if a tree is completely unbalanced (there are much more complex data structures like AVL and Red-Black Trees which balance themselves to prevent these kinds of issues).

Operation Average Runtime
search O(log(n))
insert O(log(n))
delete O(log(n))
space complexity O(n)

Exercises

Complete Part I of the exercises here.

When you're ready, move on to Binary Search Trees - Traversal

Continue

Creative Commons License