# 16.3 BST Definitions

Trees are composed of nodes and edges that connect those nodes. 

**Constraint**: there is only one path between any two nodes.

In some trees, we select a **root** node which is a node that has no parents.

A tree also has **leaves**, which are nodes with no children.

In the picture below, the green structures are valid trees, while the pink structure is not (since it has a cycle).

<figure><img src="/files/OSG4U6naLNQRUwZMu0K2" alt=""><figcaption><p>Examples of valid and invalid trees</p></figcaption></figure>

Relating this to the original tree structure we came up with earlier, we can now introduce new constraints to the already existing constraints. This creates more specific types of trees, two examples being Binary Trees and Binary Search Trees.

* **Binary Trees**: in addition to the above requirements, also hold the binary property constraint. That is, each node has either 0, 1, or 2 children.
* **Binary Search Trees**: in addition to all of the above requirements, also hold the property that For every node X in the tree:
  * Every key in the left subtree is less than X’s key.
  * Every key in the right subtree is greater than X’s key. \*\*Remember this property!! We will reference it a lot throughout the duration of this module and 61B.

<figure><img src="/files/rM19XRmPCbedYl8YI5zI" alt=""><figcaption><p>A valid BST: every key in the left subtree is smaller than its parent, and every key in the right subtree is larger.</p></figcaption></figure>

Here is the BST module we'll be using for the rest of this chapter:

```java
private class BST<Key> {
    private Key key;
    private BST left;
    private BST right;

    public BST(Key key, BST left, BST Right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }

    public BST(Key key) {
        this.key = key;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook-2025/16.-adts-and-bsts/16.3-bst-definitions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.