Updated 2022-05-22 0
Viewed 14 times
0

Hey I have this template of BinarySearchTreeNode in which i have to implement the following methods
Constructors

Destructor

Empty

leaf

Height

insert

i am done with the constructors and the insert part but i am facing issues with the destructor and the height functions please help me implement these methods Special care is required for the implementation of method height(). The empty tree has no height, hence height() must throw a domain_error exception in this case. For interior nodes, however, if a subtree of a given BinaryTreeNode is empty, then this subtree contributes a height of zero to the interior node. In other words, the smallest height of any non-empty BinaryTreeNode is zero. Remember, interior nodes add one to the maximum height of their subtrees.


Help me with these methods i am super new to DSA and c++ any help is greatly appreciated


#pragma once

#include <stdexcept>
#include <algorithm>

template <typename T>
struct BinaryTreeNode
{
    using BNode = BinaryTreeNode<T>;
    using BTreeNode = BNode *;

    T key;
    BTreeNode left;
    BTreeNode right;

    static BinaryTreeNode<T> NIL;

    const T &findMax() const
    {
        if (empty())
        {
            throw std::domain_error("Empty tree encountered.");
        }

        return right->empty() ? key : right->findMax();
    }

    const T &findMin() const
    {
        if (empty())
        {
            throw std::domain_error("Empty tree encountered.");
        }

        return left->empty() ? key : left->findMin();
    }

    bool remove(const T &aKey, BTreeNode aParent)
    {
        BTreeNode x = this;
        BTreeNode y = aParent;

        while (!x->empty())
        {
            if (aKey == x->key)
            {
                break;
            }

            y = x; // new parent

            x = aKey < x->key ? x->left : x->right;
        }

        if (x->empty())
        {
            return false; // delete failed
        }

        if (!x->left->empty())
        {
            const T &lKey = x->left->findMax(); // find max to left
            x->key = lKey;
            x->left->remove(lKey, x);
        }
        else
        {
            if (!x->right->empty())
            {
                const T &lKey = x->right->findMin(); // find min to right
                x->key = lKey;
                x->right->remove(lKey, x);
            }
            else
            {
                if (y != &NIL) // y can be NIL
                {
                    if (y->left == x)
                    {
                        y->left = &NIL;
                    }
                    else
                    {
                        y->right = &NIL;
                    }
                }

                delete x; // free deleted node
            }
        }

        return true;
    }

    // Implement theses

    BinaryTreeNode() : key(T()), left(&NIL), right(&NIL)
    {
    }
    BinaryTreeNode(const T &aKey) : key(aKey), left(&NIL), right(&NIL)
    {
    }
    BinaryTreeNode(T &&aKey) : key(std::move(aKey)), left(&NIL), right(&NIL)
    {
    }

    ~BinaryTreeNode()
    {
    }

    bool empty() const
    {
        return this == &NIL;
    }
    bool leaf() const
    {
        return left == &NIL && right == &NIL;
    }

    size_t height() const
    {
    }

    bool insert(const T &aKey)
    {
        if (aKey == key || empty())
            return false;

        if (aKey < key)
        {
            if (!left->empty())
                return left->insert(aKey);
            left = new BinaryTreeNode(aKey);
        }
        else
        {
            if (!right->empty())
                return right->insert(aKey);
            right = new BinaryTreeNode(aKey);
        }
        return true;
    }
};

template <typename T>
BinaryTreeNode<T> BinaryTreeNode<T>::NIL;
🔴 No definitive solution yet