Question

How to constructs a Binary Search Tree (BST) from a vector of numbers in C++

Answer 1

#include <iostream>
#include <memory>
#include <vector>
#include <optional>

// Represents a single node in the BST
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;

    explicit Node(int val) : value(val) {}
};

class BinarySearchTree {
public:
    // Public insertion method
    void insert(int value) {
        insert(root, value);
    }

    // Print the tree sideways
    void print() const {
        print(root.get(), 0);
    }

private:
    std::unique_ptr<Node> root;

    // Recursive BST insertion
    static void insert(std::unique_ptr<Node>& node, int value) {
        if (!node) {
            node = std::make_unique<Node>(value);
            return;
        }

        if (value < node->value) {
            insert(node->left, value);
        } else {
            insert(node->right, value);
        }
    }

    // Prints the tree rotated 90 degrees counterclockwise
    static void print(const Node* node, int depth) {
        if (!node) {
            return;
        }

        // Print right subtree first
        print(node->right.get(), depth + 1);

        // Indent according to depth
        std::cout << std::string(depth * 4, ' ')
                  << node->value << '\n';

        // Print left subtree
        print(node->left.get(), depth + 1);
    }
};

int main() {
    // Original list:
    // [4, 7, 19, 2, 3, NULL, NULL, 23, NULL, 17, 8]

    std::vector<std::optional<int>> values = {
        4, 7, 19, 2, 3, std::nullopt,
        std::nullopt, 23, std::nullopt, 17, 8
    };

    BinarySearchTree bst;

    // Insert non-NULL values only
    for (const auto& value : values) {
        if (value.has_value()) {
            bst.insert(*value);
        }
    }

    std::cout << "Binary Search Tree:\n";
    bst.print();
}


/*
          4
         / \
        2   7
         \    \
          3    19
              /  \
            17    23
           /
          8
*/


/*
run:

Binary Search Tree:
            23
        19
            17
                8
    7
4
        3
    2

*/

 

70+ SQL courses for beginners and professionals