Intro to Binary Search Trees (BSTs)

A Binary Search Tree (BST) is a data structure where each node can have up to two children, and the left child is always less than the parent, and the right child is always greater.

We use BSTs for fast searching, sorting, and organizing data.

Key Terms

Below are key terms you must know while you work with BSTs.

• Node
  A node is a single unit in the tree that holds a value. It may also have links to other nodes (its children). In the diagram, each box is a node. For example, 7, 3, 9, and 8 are all nodes in this tree. Every node can have a parent (above it), children (below it), or neither.

• Root
  The root is the very first node at the top of the tree. It has no parent. In the diagram, 7 is the root because it’s where everything starts and it connects to the rest of the nodes below it.

• Parent
  A parent is any node that has one or more children linked below it. In the diagram, 7 is a parent to both 3 and 9, and 9 is a parent to 8.

• Child
  A child is any node that is connected below another node. It always has a parent above it. In the diagram, 3, 9, and 8 are all children.

• Leaf
  A leaf is a node that does not have any children. It sits at the very end of a branch. In the diagram, 3 and 8 are leaves because nothing comes after them.

• Branch
  A branch is a path from one node to another. For example, starting at 7 and going to 9, then to 8, forms one branch in the tree. There can be multiple branches in a tree.