CODEWITHSUNDEEP
c++binary-search-tree
juice
juice

Reputation: 15

How to print ALL BST nodes with values between min and max

I have the following BST for reference. BST

Assume that min: 9 and max: 20 It satisfies all the criteria such that for each node (X), all the nodes in the left substree are smaller than, and all the nodes in the right substree are bigger than the value of X.

I'm having trouble creating a function (member function so it has access to the root node) that prints ALL the values. Specifically, say that my current Node is 10, but I would still need to check both the left and right subtree. I cannot pass the node in the parameter (otherwise I could do something like this?), so I have to implement this function

void printBetween(int min, int max);

Also, the function should only visits a subtree where the values may be valid.

Assume that the node struct looks like this:

struct Node{
        T data_;
        Node* left_;
        Node* right_;
        Node(const T& data, Node* left=nullptr, Node* right=nullptr){
            data_=data;
            left_=left;
            right_=right;
        }        
    };

How would I go about if both the left child and the right child could have a value between min and max?

void printBetween(int min, int max){
    // left child: smaller than
    // right child: bigger than
    // This function prints every value in the tree that is between min and max inclusive.

    if( root_ == nullptr)
        cout << "No values found" << endl;
    Node* currNode = root_;

   // check until currNode is a valid node 
    while(currNode != nullptr){
        // print value if currNode's data value is between min and max inclusive,
        if(currNode->data_ > min && currNode->data_ <= max){
            cout << "Value: " << data_ << "," << endl;
            fnd = true;
            // since it falls in the range, have to check both children
            // not sure what to do here??
            if(currNode != nullptr && currNode->left_->data_ > min && currNode->left_->data_ <= max){
                 currNode = currNode->left_;   
            } else if(currNode != nullptr && currNode->right_->data_ > min && currNode->right_->data_ <= max){
                 currNode = currNode->right_; 
            }
        }

        // current node's data is too big, so go to its left child
        if(currNode->data_ > max){
            currNode = currNode->left_;
        } 
        // current node's data is too small, so go to its right child
        else if(currNode->data_ < min){
            currNode = currNode->right_;
        } 
    }
}

Upvotes: 1

Views: 547

Answers (1)

Ted Lyngmo
Ted Lyngmo

Reputation: 117318

First, there's a small problem with void printBetween(int min, int max);. int should be T. You should also consider taking min and max by const& in case your BST is used with types that are expensive to copy.

How would I go about if both the left child and the right child could have a value between min and max?

In those cases, you need to search them both. You could add a helper member function that you call recursively. I call it printer() in the example below. Your printBetween() will only be used to call printer() with the starting value root_.

void printer(const T& min, const T& max, Node* currNode) {
    if(currNode == nullptr) return; // end of branch, return

    if(currNode->data_ >= min && currNode->data_ <= max) {     // [min, max]
        // we got a match, both branches must be followed

        printer(min, max, currNode->left_); // call printer for the smaller values

        std::cout << "Value: " << currNode->data_ << '\n';

        printer(min, max, currNode->right_); // call printer for the greater values

    } else if(currNode->data_ < min) {
        // data is less than min, no need to search the left branch
        printer(min, max, currNode->right_);

    } else {
        // data is greater than max, no need to search the right branch
        printer(min, max, currNode->left_);
    }
}

void printBetween(const T& min, const T& max) {
    printer(min, max, root_);
}

Another note: If you are going to use your BST with types that aren't default constructibe, you need to use the member initializer list in Node.

Example:

struct Node {
    T data_;
    Node* left_;
    Node* right_;

    Node(const T& data, Node* left=nullptr, Node* right=nullptr) :
        data_(data),
        left_(left),
        right_(right)
    {
        // empty function body
    }        
};

Demo

Upvotes: 1

Related Questions