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:

1. The convention for binary tree diagrams is that the root is at the top, and the subtrees branch down from it.
2. 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.
3. A non-root node with no children is called a leaf.
4. 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.
5. 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 .
6. The depth (or level) of some node is its distance (i.e., number of edges) from the tree's root node.
7. 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:

1. The root node is .
2. The respective left and right children of are and . The left child of is . The respective left and right children of are and .
3. Nodes , , and are leaves (i.e., each node is a leaf).
4. The root is the ancestor of all other nodes, is an ancestor of , and is an ancestor of and .
5. The path between and is . The path between and is . The path between and is .
6. The depth of root node is . The depth of nodes and is . The depth of nodes , , and , is .

7. 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:

1. Each element in the left subtree of is less than or equal to the root element of (i.e., ).
2. Each element in the right subtree of is greater than the root element of (i.e., ).
3. 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.

Solve Problem