1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

/* BST = Binary Search Tree
 *
 * ... a particular kind of tree.
 *
 * Q: What is a tree?
 * A: Dynamic structure like a linked list but with more than one "out link".
 *    IOW, instead of .next, you have .left and .right  (in the case of a
 *    "binary" tree).
 *
 */

typedef struct _BSTNode {
    int value;
    struct _BSTNode* left;
    struct _BSTNode* right;
} BSTNode;

// Reminder:  You can't refer to the shortcut name (BSTNode) until you get to it,
// so you have to use the long name (struct _BSTNode) within the struct definition.





/* Binary tree of size 1.  The root is [∙ | 6 | ∙].  It has no children (yet).
 *
 *              root  (like the head in a linked list)
 *                ↓
 *           [∙ | 6 | ∙ ]
 *            ↓       ↓
 *           NULL    NULL
 *
 * Binary search tree
 * Each node has a value.
 * node -> left ->  value must be less    than               node -> value
 * node -> right -> value must be greater than (or equal to) node -> value
 *
 *               root  (like the head in a linked list)
 *                ↓
 *           [∙ | 6 | ∙ ]
 *            ↓       ↓
 *    [∙ | 4 | ∙]    [∙ | 8 | ∙]     ← leaf nodes
 *     ↓       ↓      ↓       ↓       
 *   NULL     NULL    NULL   NULL
 *
 * Leaf node is a node that has no children.
 *
 * Root node is a node that is not the child of any other node.
 *
 * Binary search trees let you do something similar to binary search.
 *
 *                         root  (like the head in a linked list)
 *                          ↓
 *                     [∙ | 6 | ∙ ]
 *                      ↓       ↓
 *              [∙ | 4 | ∙]    [∙ | 8 | ∙]
 *               ↓       ↓      ↓       ↓       
 *         [∙|3|∙]  [∙|5|∙]  [∙|7|∙]   [∙|9|∙]
 *
 *
 * Q:  Is 9 in the structure above?
 * A:  Clearly yes, but with a BST, it is faster to find out.
 *
 * With a linked list, you would have to go through the whole list.
 * Assuming it is not sorted:
 *
 * 4 → 8 → 7 → 9 → 3 → 5 → 6
 *
 *
 * To add a new number to the BST, we start at the root.
 *
 * If the root is NULL, then add it at the root.  This just like
 * the first node in a linked list.
 *
 * Just like an empty linked list is NULL, so is an empty BST.
 *
 * Left subtree of the above tree rooted at […|6|…]:
 *
 *              [∙ | 4 | ∙]
 *               ↓       ↓
 *         [∙|3|∙]      [∙|5|∙]
 *
 *
 * Left subtree of the above tree rooted at […|4|…]:
 *
 *         [∙|3|∙]
 *          ↓   ↓
 *       NULL   NULL
 *
 *
 * Left subtree of the above tree rooted at […|3|…]:
 *
 *         NULL  (empty tree)
 */

// DO NOT COPY THIS CODE (Reminder:  Our code is not fair game unless it
// explicitly says "Okay to copy/adapt" (or similar).  Your code may
// come out very similar, but you should write it without looking at
// this.

void insert(int value, BSTNode** a_root) {
    if(*a_root == NULL) { // is this an empty tree
        // Create a new node
        BSTNode* new_node = {.value = value, .left=NULL, .right=NULL};
        *a_root = new_node;
    }
    else if(value < (*a_root) -> value) {
        insert(value, &(*a_root) -> left);
    }
    else {
        insert(value, &(*a_root) -> right);
    }
}

int main(int argc, char* argv[]) {
    // Empty tree

    BSTNode* root = NULL;  // just like with an empty linked list
    // Type of  root is BSTNode*  (address of a BSTNode)
    // Type of &root is BSTNode** (address of an address of a BSTNode)

    insert(6, &root);

    
    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */

© Copyright 2020 Alexander J. Quinn         This content is protected and may not be shared, uploaded, or distributed.