BST insertion and destruction

This lesson contains approximately 25 minutes of video content.

Insertion that satisfies the BST property

Destruction of BST

Activity: Insert behavior and destructor for a binary search tree

Graded Playground Autograder

Activity Prompt:

In this programming problem, you will implement a Insert behavior and destructor for a binary search tree type. While we only require you to define that member function, you might want to define different behaviors to test your implementation. The binary search tree property used in this activity follows that from the video:

  • Let x be a node in the BST.
    • If y is a node in the left subtree of x, then y.value < x.value.
    • If y is a node in the right subtree of x, then y.value >= x.value.
Member functions you are to implement
public:
void Insert(const T& value); Creates a new node with value and inserts that node into the binary search tree respecting the binary search tree property. Don't forget about the empty tree condition.
~Bst(); Destructor. Deallocates all dynamic memory associated with the binary search tree.
Provided member functions
public:
Bst() = default; Default constructor.
Data members
private:
Node<T>* root_ = nullptr; Pointer to the root of the binary search tree.
#include <iostream> #include "bst.hpp" #include "bst_node.hpp" int main() {}
#ifndef BST_HPP #define BST_HPP #include "bst_node.hpp" template <typename T> class Bst { public: // assigned // void Insert(const T& value); // ~Bst(); // provided Bst() = default; private: Node<T>* root_ = nullptr; }; #endif
#include "bst.hpp"
#ifndef NODE_HPP #define NODE_HPP // DO NOT MODIFY THIS FILE: OUR GRADER USES THE ORIGINAL bst_node.hpp PROVIDED // TO YOU. WE DO NOT COPY THIS FILE FROM YOUR WORKSPACE TO OUR AUTO-GRADER. template <typename T> struct Node { T value; // NOLINT Node<T>* parent = nullptr; // NOLINT Node<T>* left = nullptr; // NOLINT Node<T>* right = nullptr; // NOLINT Node() = default; Node(T value): value(value) {} }; #endif