BST queries (part 2)

This lesson contains approximately 20 minutes of video content.

Successor

Successor cases

I should have explicitly listed the "cases" considered in finding some node's successor; they are (in this order):

  1. node has right-subtree
  2. node does not have a right-subtree and is left of its parent
  3. node does not have a right-subtree and is right of its parent

Activity: Find node's successor in a binary search tree

Graded Playground Autograder

Activity Prompt:

In this programming problem, you will implement a SuccessorNode 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>* SuccessorNode(Node<T>* node); Searches the binary search tree for the successor of node and returns the address of the successor node to the caller. If the node does not have a successor, the behavior returns nullptr.
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" int main() { }
#ifndef BST_HPP #define BST_HPP #include "bst_node.hpp" template <typename T> class Bst { public: // assigned // Node<T>* SuccessorNode(Node<T>* node); // 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"
#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