c++recursionbinary-tree

Coding remove() function for a Binary Tree


I'm in a data structures class and we have to code a Binary Tree (not a Binary Search Tree). I have like 90% of it working but I'm having trouble getting my remove() function to work.

For reference, we're making a class BinaryTree that must have the following functions

template <class ItemType>
class BinaryTree {
    private:
     std::shared_ptr<BinaryNode<ItemType>> rootptr;

    protected:
     // Removes the target value from the tree
     virtual std::shared_ptr<BinaryNode<ItemType>
     removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
                  const ItemType& target, bool isSuccessful);

     // Copies values up the tree to overwrite value in current
     // node until a leaf is reached; the leaf is then removed,
     // since its value is stored in the parent.
     std::shared_ptr<BinaryNode<ItemType>>
     moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>>
                      subTreePtr);

      // other { working } methods

    public:
     // Removes specified item from the tree
     bool remove(const ItemType& data);

     // other { working } methods
}

The interface for the BinaryNode class (which was provided to us) is:

template <class ItemType>
class BinaryNode {
    private:
     ItemType item;
     std::shared_ptr<BinaryNode<ItemType>> leftChildPtr;
     std::shared_ptr<BinaryNode<ItemType>> rightChildPtr;
    public:
     // returns true if node has no children
     bool isLeaf() const;

     // other typical methods (constructors, getters, setters)
}

So far I've tried the following implementation for my moveValuesUpTree function:

std::shared_ptr<BinaryNode<ItemType>> BinaryNodeTree<ItemType>::
    moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>>
                     subTreePtr) {

    if(subTreePtr) {
        if(!subTreePtr->isLeaf()) {
            if(subTreePtr->getLeftChildPtr()) {
                subTreePtr->setItem(subTreePtr->getLeftChildPtr()
                                    ->getItem());
                moveValuesUpTree(subTreePtr->getLeftChildPtr());
            } else if(subTreePtr->getRightChildPtr()) {
                subTreePtr->setItem(subTreePtr->getRightChildPtr()
                                    ->getItem());
                moveValuesUpTree(subTreePtr->getRightChildPtr());
            } // end if
        } // end if
    } // end if
    return subTreePtr;
} // end moveValuesUpTree

This function works in moving the values up the tree. I was thinking that in coding the removeValue() function I could just move the value of the node I want to remove to the bottom of the tree and then delete it (that way it's always a leaf and you don't have to worry about reconnecting any nodes), but the moveValuesUpTree functions erases the value that I want to get rid of. Is there any way to preserve this value in the recursive moveValuesUpTree function above and then store it in the leaf? Or is there a better way to go about using the two protected methods in conjunction to remove a value?

Thanks!

Edit: The moveValuesUpTree function doesn't get rid of the node -- just the value. So for example, a call of moveValuesUpTree(2) on a tree whose (postorder) output is 74625381 would be 77645831.


Solution

  • Instead of moving the value to the last leaf and then delete the leaf, you should delete it when you are moving the values up since it is at this moment you will find the leaf and will know his exact position. What I would suggest is to test if the left or right child of the current node is a leaf and if it is, delete it since you already move the value of it in the current node.

    std::shared_ptr<BinaryNode<ItemType>> BinaryNodeTree<ItemType>::
    moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>>subTreePtr) {
    
        if(subTreePtr) {
            if(!subTreePtr->isLeaf()) {
                if(subTreePtr->getLeftChildPtr()) {
                    subTreePtr->setItem(subTreePtr->getLeftChildPtr()->getItem());
    
                    if(subTreePtr->getLeftChildPtr()->isLeaf())
                        //Delete left child here
                    else
                        moveValuesUpTree(subTreePtr->getLeftChildPtr());
                  } else if(subTreePtr->getRightChildPtr()) {
                    subTreePtr->setItem(subTreePtr->getRightChildPtr()->getItem());
    
                    if(subTreePtr->getRightChildPtr()->isLeaf())
                        //Delete right child here
                    else
                         moveValuesUpTree(subTreePtr->getRightChildPtr());
                } // end if
            } // end if
        } // end if
        return subTreePtr;
    } // end moveValuesUpTree