I need to traverse a binary search tree and find the nth item, I'm able to successfully traverse the tree, however when I try to implement a limit, or endpoint, to stop at the nth item--returning its value, I can't get my counter to increment. I've tried about fifty different ways to get the counter to increase without avail.

I currently have the counter implemented as a class attribute so it remains outside the scope of a single call for the recursive function. To help me troubleshoot and learn I tried to have it print out the value at the node as well as the position, and that's how I realized that my counter won't increment.

Desired result:

10 (position 1)
25 (position 2)
32 (position 3)
...

Current Results:

10 (position 1)
25 (position 1)
32 (position 1)
...

Here's my class:

class BST {
  public:
  int data;
  int counter = 0;
  BST *left, *right;
  BST();
  BST(int);
  ~BST();
  void insert(int val);
  int nth_node(int n);
  int size();
};

as well as my nth_node function:

int BST::nth_node(int n) {
    
    /*
    // Check to see if we've hit the limiter.
    if (counter == n) {
        std::cout << std::endl<< std::endl << "ITEM FOUND!!!" << std::endl<< std::endl;
        counter = 0; //reset the counter
        return data;
    } */
    
    if (counter <= n) { // Haven't hit the limiter, so do in_order transversal
    
        // Go left
        if (left != nullptr){
            left -> nth_node(n);
        }
        
        // Go middle
        counter  ;
        std::cout << data << " (position: " << counter << "), " << std::endl ;
        
        // Go Right
        if (right != nullptr){
            right -> nth_node(n);
        }
    }
    
    
    return data;
}

CodePudding user response：

Using a member variable of one node of the tree won't work. The different nodes have different counter variables. In your code every counter variable is decreased at most once and even worse it's never initialized resulting in undefined behaviour.

You need to introduce a helper function here, unless you want to first query the subtree and later possibly recursively call the function for the same subtree.

Note: the examples below assume n to be 1-based, i.e. 1 is used to get the smallest value, 2, for the second smallest one, ect.

You could pass n by reference to the helper function. This way you use an "alias" for the variable (parameter) declared in the member function for every recursive call.

namespace
{

    /**
     * \param[in,out] n     in: the 1 based index of the node to find;
     *                     out: the original value minus the number of nodes searched
     * 
     * \return nullptr, if not found, the node found otherwise 
     */
    BST const* NthElementHelper(BST const& tree, int& n)
    {
        int size = 1;
        
        if (tree.m_left != nullptr)
        {
            auto leftResult = NthElementHelper(*tree.m_left, n);
            if (leftResult != nullptr)
            {
                // node found in left subtree
                return leftResult;
            }
        }
        
        if (n == 1)
        {
            return &tree;
        }
        --n;
        
        if (tree.m_right != nullptr)
        {
            return NthElementHelper(*tree.m_right, n);
        }
        return nullptr;
    }
}

int BST::nth_node(int n)
{
    if (n <= 0)
    {
        throw std::runtime_error("n needs to be positive");
    }

    auto findResult = NthElementHelper(*this, n);
    if (findResult == nullptr)
    {
        throw std::runtime_error("there are no n nodes in the tree");
    }
    return findResult->m_data;
}

Alternatively you could return the node or the subtree size depending on whether you've found the node or not:

namespace
{

    std::variant<BST const*, int> NthElementHelper(BST const& tree, int n)
    {
        int size = 1;
        
        if (tree.m_left != nullptr)
        {
            auto leftResult = NthElementHelper(*tree.m_left, n);
            if (leftResult.index() == 0)
            {
                // node found
                return leftResult;
            }
            auto subtreeSize = std::get<int>(leftResult);
            size  = subtreeSize;
            n -= subtreeSize;
        }
        
        if (n == 1)
        {
            return &tree;
        }
        --n;
        
        if (tree.m_right != nullptr)
        {
            auto rightResult = NthElementHelper(*tree.m_right, n);
            if (rightResult.index() == 0)
            {
                return rightResult;
            }
            auto subtreeSize = std::get<int>(rightResult);
            size  = subtreeSize;
        }
        return { size };
    }
}

int BST::nth_node(int n)
{
    if (n <= 0)
    {
        throw std::runtime_error("n needs to be positive");
    }

    auto findResult = NthElementHelper(*this, n);
    if (findResult.index() != 0)
    {
        throw std::runtime_error("there are no n nodes in the tree");
    }
    return std::get<BST const*>(findResult)->m_data;
}

CodePudding user response：

You can make counter a function argument, and for convenience set a default value:

int BST::nth_node(int n, int counter = 0)
{
    
    /*
    // Check to see if we've hit the limiter.
    if (counter == n) {
        std::cout << std::endl<< std::endl << "ITEM FOUND!!!" << std::endl<< std::endl;
        counter = 0; //reset the counter
        return data;
    } */
    
    if (counter <= n) { // Haven't hit the limiter so do in_order transversal
    
        // Go left
        if (left != nullptr){
            left -> nth_node(n, counter);
        }
        
        // Go middle
        counter  ;
        std::cout << data << " (position: " << counter << "), " << std::endl ;
        
        // Go Right
        if (right != nullptr){
            right -> nth_node(n, counter);
        }
    }
    
    
    return data;
}