# Day 22: Binary Search Trees

# Day 22: Binary Search Trees

Terms you'll find helpful in completing today's challenge are outlined below, along with sample Java code (where appropriate).

## Binary Tree

Fundamentally, a binary tree is composed of nodes connected by edges (with further restrictions discussed below). Some binary tree, , is either empty or consists of a single *root* element with two distinct binary tree child elements known as the *left subtree* and the *right subtree* of . As the name *binary* suggests, a node in a binary tree has a *maximum* of children.

The following diagrams depict two different binary trees:

Here are the basic facts and terms to know about binary trees:

- The convention for binary tree diagrams is that the
*root*is at the top, and the subtrees branch down from it. - A node's
*left*and*right*subtrees are referred to as*children*, and that node can be referred to as the*parent*of those subtrees. - A non-root node with no children is called a
*leaf*. - Some node is an
*ancestor*of some node if is located in a left or right subtree whose*root*node is . This means that the*root*node of binary tree is the ancestor of all other nodes in the tree. - If some node is an ancestor of some node , then the
*path*from to is the sequence of nodes starting with , moving down the ancestral chain of children, and ending with . - The
*depth*(or*level*) of some node is its distance (i.e., number of edges) from the tree's root node. - Simply put, the
*height*of a tree is the number of edges between the*root*node and its furthest leaf. More technically put, it's (i.e., one more than the maximum of the heights of its left and right subtrees). Any node has a height of , and the height of an empty subtree is . Because the height of each node is the maximum height of its subtrees and an empty subtree's height is , the height of a single-element tree or leaf node is .

Let's apply some of the terms we learned above to the binary tree on the *right*:

- The
*root*node is . - The respective left and right children of are and . The left child of is . The respective left and right children of are and .
- Nodes , , and are leaves (i.e., each node is a leaf).
- The root is the ancestor of all other nodes, is an ancestor of , and is an ancestor of and .
- The path between and is . The path between and is . The path between and is .
- The depth of root node is . The depth of nodes and is . The depth of nodes , , and , is .
The height of the tree, , is . We calculate this recursively as . Because this is long and complicated when expanded, we'll break it down using an image of a slightly simpler version of whose height is still :

In the diagram above, the height of is because that is the maximum height of 's left and right subtrees.

## Binary Search Tree

A *Binary Search Tree* (BST), , is a binary tree that is either empty or satisfies the following three conditions:

- Each element in the left subtree of is less than or equal to the root element of (i.e., ).
- Each element in the right subtree of is greater than the root element of (i.e., ).
- Both and are BSTs.

You can essentially think of it as a regular binary tree where for each node *parent* having a and , . In the diagram above, the binary tree of integers on the left side is a binary search tree.