BST queries (part 1)

This lesson contains approximately 25 minutes of video content.

Binary search tree review

Minimum and maximum

Searching

Activity: Find node with value in a binary search tree

Graded Playground Autograder

Activity Prompt:

In this programming problem, you will implement a FindNode behavior 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:
Node<T>* FindNode(T value); Searches the binary search tree for the node whose value is value and returns the address of that node to the caller. If the node is not found, the behavior returns nullptr. Assume that there is at most one node in the tree with value.
Provided member functions
public:
Bst(T root_value); Parameterized constructor. Creates a new node whose value is root_value; assigns the address of that node to root_.
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 // Node<T>* FindNode(T value); // provided Bst(T root_value); private: Node<T>* root_ = nullptr; }; template <typename T> Bst<T>::Bst(T root_value) { root_ = new Node<T>(root_value); } #endif
#include "bst.hpp" // ... function template definitions must go in the header file, not here.
#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