# Binary Search Tree Homework Solutions

**Assignment:** Written Portion (BST Insertion & Traversals)

---

## Problem 1: BST Insertion Sequences

Draw the binary search tree that results from inserting each sequence of numbers into an initially empty tree.

> **Rules for Binary Search Tree Insertion:**
> 1. The first inserted value becomes the **Root**.
> 2. For each subsequent value, compare it with the current node:
>    - If the value is **less than** the current node, move to the **left child**.
>    - If the value is **greater than** the current node, move to the **right child**.
> 3. Repeat until an empty spot is found, then insert the value as a new leaf node.

---

### Sequence A

**Sequence:** `8, 3, 10, 1, 6, 14, 4, 7, 13`

#### Insertion Steps:
* **8:** Root node.
* **3:** $3 < 8 \rightarrow$ Left child of `8`.
* **10:** $10 > 8 \rightarrow$ Right child of `8`.
* **1:** $1 < 8, 1 < 3 \rightarrow$ Left child of `3`.
* **6:** $6 < 8, 6 > 3 \rightarrow$ Right child of `3`.
* **14:** $14 > 8, 14 > 10 \rightarrow$ Right child of `10`.
* **4:** $4 < 8, 4 > 3, 4 < 6 \rightarrow$ Left child of `6`.
* **7:** $7 < 8, 7 > 3, 7 > 6 \rightarrow$ Right child of `6`.
* **13:** $13 > 8, 13 > 10, 13 < 14 \rightarrow$ Left child of `14`.

#### Tree Structure:

```text
          8
        /   \
       3     10
      / \      \
     1   6     14
        / \    /
       4   7  13
```

---

### Sequence B

**Sequence:** `15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9`

#### Insertion Steps:
* **15:** Root node.
* **6:** $6 < 15 \rightarrow$ Left child of `15`.
* **18:** $18 > 15 \rightarrow$ Right child of `18`.
* **3:** $3 < 15, 3 < 6 \rightarrow$ Left child of `6`.
* **7:** $7 < 15, 7 > 6 \rightarrow$ Right child of `6`.
* **17:** $17 > 15, 17 < 18 \rightarrow$ Left child of `18`.
* **20:** $20 > 15, 20 > 18 \rightarrow$ Right child of `18`.
* **2:** $2 < 15, 2 < 6, 2 < 3 \rightarrow$ Left child of `3`.
* **4:** $4 < 15, 4 < 6, 4 > 3 \rightarrow$ Right child of `3`.
* **13:** $13 < 15, 13 > 6, 13 > 7 \rightarrow$ Right child of `7`.
* **9:** $9 < 15, 9 > 6, 9 > 7, 9 < 13 \rightarrow$ Left child of `13`.

#### Tree Structure:

```text
           15
         /    \
        6      18
       / \    /  \
      3   7  17  20
     / \   \
    2   4   13
           /
          9
```

---

## Problem 2: Tree Traversals

Given the binary search trees, determine the node visit order for **Preorder**, **Inorder**, and **Postorder** traversals.

---

### Tree 1

```text
      8
     / \
    3   10
   / \    \
  1   6   14
     / \  /
    4  7 13
```

#### Traversal Definitions & Order:

1. **Preorder (Root, Left, Right)**
   * **Order:** `8, 3, 1, 6, 4, 7, 10, 14, 13`

2. **Inorder (Left, Root, Right)**
   * **Order:** `1, 3, 4, 6, 7, 8, 10, 13, 14`

3. **Postorder (Left, Right, Root)**
   * **Order:** `1, 4, 7, 6, 3, 13, 14, 10, 8`

---

### Tree 2

```text
      20
     /  \
    10   30
   / \  / \
  5  15 25 35
 /    \
2     18
```

#### Traversal Definitions & Order:

1. **Preorder (Root, Left, Right)**
   * **Order:** `20, 10, 5, 2, 15, 18, 30, 25, 35`

2. **Inorder (Left, Root, Right)**
   * **Order:** `2, 5, 10, 15, 18, 20, 25, 30, 35`

3. **Postorder (Left, Right, Root)**
   * **Order:** `2, 5, 18, 15, 10, 25, 35, 30, 20`