Home | Projects | Notes > Data Structures & Algorithms > Trees

Trees

Binary Trees Terminology

Full binary tree
- Every node points to either 0 or 2 nodes
Complete binary tree
- All levels, except possibly the last one, are completely filled, and the last level is filled from left to right with no missing nodes.
- Not "perfect" since the bottom level is not filled all the way across
Perfect binary tree
- Any level of a binary tree that has any nodes is perfectly filled all the way across
- All perfect binary trees are both "complete" and "full"
Siblings
- Nodes that share the same parent
- In a tree, each node (except for the root node) has exactly one parent.
Leaf node
- Any node in a tree that has no children
Internal node (a.k.a. inner node or non-leaf node)
- Any node in a tree that is not a leaf node
- Root node is also an internal node.

Binary Search Trees (C++)

A binary search tree (BST) is a binary tree data structure in which each node has a key/value associated with it, and the keys satisfy the following properties:

All operations have O(log n) time complexity, which is very efficient. (Every time you go down one level, you are excluding the half of the remaining nodes from your search.)
$\to$ Divide and conquer!
If a tree never forks, it is essentially a linked list, in which case the search time complexity will be O(n). However, since this is not a general case, a binary search tree is still treated as an O(log n) data structure.

Interface


xxxxxxxxxx
36
1
//==============================================================================
2
// File     : binary_search_tree.h
3
// Brief    : Interface for Binary Search Tree (BST)
4
// Author   : Kyungjae Lee
5
// Date     : Jun 29, 2023
6
//==============================================================================
7

8
#ifndef BINARY_SEARCH_TREE_H
9
#define BINARY_SEARCH_TREE_H
10

11
// Class for binary search tree nodes
12
class Node
13
{
14
public:
15
    int value;
16
    Node *left;         // Pointer to the left child
17
    Node *right;        // Pointer to the right child
18

19
    Node(int value);    // Constructor
20
};
21

22
// Class for binary search tree
23
class BinarySearchTree
24
{
25
public:    
26
    // Public interface
27
    BinarySearchTree(void);     // Constructor  
28
    ~BinarySearchTree(void);    // Destructor
29
    bool insert(int value);     // Inserts a node into the BST
30
    bool contains(int value);   // Checks if the BST contains the passed node
31

32
//private:
33
    Node *root;
34
};
35

36
#endif // BINARY_SEARCH_TREE_H

Implementation


xxxxxxxxxx
111
1
//==============================================================================
2
// File     : binary_search_tree.cpp
3
// Brief    : Implementation of Binary Search Tree (BST)
4
// Author   : Kyungjae Lee
5
// Date     : Jun 29, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include "binary_search_tree.h"
10

11
using namespace std;
12

13
//------------------------------------------------------------------------------
14
// Implementation of Node class interface
15
//------------------------------------------------------------------------------
16

17
// Constructor
18
// T = O(1)
19
Node::Node(int value)
20
{
21
    this->value = value;
22
    left = nullptr;
23
    right = nullptr;
24
} // End of Node constructor
25

26
//------------------------------------------------------------------------------
27
// Implementation of Binary Search Tree class interface
28
//------------------------------------------------------------------------------
29

30
// Constructor
31
// T = O(1)
32
BinarySearchTree::BinarySearchTree(void)
33
{
34
    root = nullptr;
35
} // End of BinarySearchTree constructor
36

37
// Inserts a node into the BST
38
// T = O(log n); Technically O(log n) since the Big-O measures the worst case
39
bool BinarySearchTree::insert(int value)
40
{
41
    Node *newNode = new Node(value);
42

43
    if (root == nullptr)
44
    {
45
        // Handle inserting a node into an empty BST
46
        root = newNode;
47
        return true;
48
    }
49

50
    Node *curr = root;
51
    
52
    while (true)
53
    {
54
        if (newNode->value == curr->value)
55
        {
56
            // Do not allow inserting a node whose value is already present in
57
            // the BST
58
            return false;
59
        }
60
        else if (newNode->value < curr->value)
61
        {
62
            // newNode with the smaller value goes to the left
63
            if (curr->left == nullptr)
64
            {
65
                // Spot is empty, so insert the newNode there
66
                curr->left = newNode;
67
                return true;
68
            }
69
            else
70
            {
71
                // Spot is not empty, advance the curr and keep searching
72
                curr = curr->left;
73
            }
74
        }
75
        else
76
        {
77
            // newNode with the greater value goes to the right
78
            if (curr->right == nullptr)
79
            {
80
                // Spot is empty, so insert the newNode there
81
                curr->right = newNode;
82
                return true;
83
            }
84
            else
85
            {
86
                // Spot is not empty, advance the curr and keep searching
87
                curr = curr->right;
88
            }
89

90
        }
91
    }
92
} // End of insert */
93

94
// Checks if the BST contains the passed node
95
// T = O(log n); Technically O(log n) since the Big-O measures the worst case
96
bool BinarySearchTree::contains(int value)
97
{
98
    Node *curr = root;
99

100
    while (curr)
101
    {
102
        if (value < curr->value)
103
            curr = curr->left;
104
        else if (value > curr->value)
105
            curr = curr->right;
106
        else
107
            return true;
108
    }
109

110
    return false;
111
} // End of contains

Test Driver


xxxxxxxxxx
33
1
//==============================================================================
2
// File     : main.cpp
3
// Brief    : Test driver for Binary Search Tree (BST)
4
// Author   : Kyungjae Lee
5
// Date     : Jun 29, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include "binary_search_tree.h"
10

11
using namespace std;
12

13
int main(int argc, char *argv[])
14
{
15
    // Create a BST
16
    BinarySearchTree *bst = new BinarySearchTree();
17
    
18
    // Insert nodes
19
    bst->insert(47);
20
    bst->insert(21);
21
    bst->insert(76);
22
    bst->insert(18);
23
    bst->insert(57);
24
    bst->insert(82);
25
    bst->insert(27);
26

27
    cout << bst->root->left->right->value << endl;          // 27
28

29
    cout << "Contains 27: " << bst->contains(27) << endl;   // 1
30
    cout << "Contains 17: " << bst->contains(17) << endl;   // 0
31

32
    return 0;
33
}


xxxxxxxxxx
3
1
27
2
Contains 27: 1
3
Contains 17: 0