How to find nodes value is greater than a specified value in a binary search tree

Question

Hi,

I have a red black tree and the basic operations insert, delete, traversing inorder, postorder and preorder etc.

I wish to create a method that can return the nodes in the tree that are greater than a specified value. Same with less than too.

Can anyone point me to some pseudocode / algorithm (they probably mean the same thing)

Cheers

Answer 1

Below is the code I have created which tests fine for displaying my nodes in ascending order for nodes greater than or equal to a specified value. Can someone please review my code and recommend improvements and if possible recommend how I may do this for my LessThan method. Currently my LessThan method returns in descending order and I just can not see how to get it ascending. Cheers.

 // --------------------------------------------------------------------------------
// GetNodesGreaterThan
// --------------------------------------------------------------------------------
/** \fn void  RedBlackTree<T>::GetNodesGreaterThan(T &data)
 *  \brief This method checks to see if tree is empty otherwise calls the 
 *          recursive the GreaterThan method.
 *  \param templated
 *  \return void
 */
template <class T>
void  RedBlackTree<T>::GetNodesGreaterThan(T &data)
{
    GreaterThan(m_root, data);
}

// --------------------------------------------------------------------------------
// GreaterThan
// --------------------------------------------------------------------------------
/** \fn void RedBlackTree<T>::GreaterThan(NodeType<T> *p, const T &data) const
 *  \brief This method finds the nodes in the tree that are greater than  or equal to 
 *          a specified value and puts nodes into a list.
 *  \param templated pointer
 *  \param constant template
 *  \return void
 */
template <class T>
void RedBlackTree<T>::GreaterThan(NodeType<T> *p, const T &data) const
{
    if ( p != NULL)                                         // we have hit a leaf node
    {
        if ((p->m_data == data) || (data < p->m_data)){     // record the node whos value is
            GreaterThan(p->m_lLink, data);                  // move down left link
            //cout << p->m_data << " ";                     // Display data (debug purpose)
        }
        GreaterThan(p->m_rLink, data);                      // move down right link 
    }
}

// --------------------------------------------------------------------------------
// GetNodesLessThan
// --------------------------------------------------------------------------------
/** \fn void  RedBlackTree<T>::GetNodesLessThan(T &data)
 *  \brief This method checks to see if tree is empty otherwise calls the 
 *          recursive the LessThan method.
 *  \param template
 *  \return void
 */
template <class T>
void  RedBlackTree<T>::GetNodesLessThan(T &data)
{
    ClearList();                                            // clears the node list
    LessThan(m_root, data);
}

// --------------------------------------------------------------------------------
// LessThan
// --------------------------------------------------------------------------------
/** \fn void RedBlackTree<T>::LessThan(NodeType<T> *p, const T &data) const
 *  \brief This method finds the nodes in the tree that are less than  or equal to 
 *          a specified value and puts nodes into a list.
*  \param templated pointer
 *  \param constant template
 */
template <class T>
void RedBlackTree<T>::LessThan(NodeType<T> *p, const T &data) const
{
    if ( p != NULL)
    {
        if ((p->m_data == data) || (data > p->m_data)){     // record the node whos value is
            LessThan(p->m_rLink, data);                     // move down left link
            //cout << p->m_data << " ";                     // Display data (debug purpose)
            //m_list[m_countOfElements] = p->m_data;            // add to list
            //m_countOfElements++;                              // increment # of elements
        }
        LessThan(p->m_lLink, data);                         // move down left link
    }
}