CODEWITHSUNDEEP
c++binary-search-treenodes
Eddy
Eddy

Reputation: 47

How would I find the height of each node and assign it postorder in a binary search tree?

I have a templated class with an additional Node class with a height attribute. I want to be able to validate the height of each node after a new node has been inserted. My insert node function is working well, I am just confused on how I would change the height of each node after a new node is inserted.

template <typename T>
class BST
{
public:
    class Node 
    {
    public:
        T key;
        int height = 0;    
        Node* left = nullptr;
        Node* right = nullptr;
        Node* parent = nullptr;
       
        Node(){}
       
        Node(T k, Node* input_node = nullptr)
        {
            key = k;
            parent = input_node;
        }
    };

private:
   
    Node* root_ = nullptr;
    unsigned int size_ = 0;

public:

   BST(); 

   ~BST();

   void insert(T k);

private: 

    void fix_height(Node* node);


template <typename T>
void BST<T>::insert(T k)
{
    
    Node* node = root_; // insert function 
    Node* prev_node = node;
    bool went_right;

    if(node == nullptr)
    {
        root_ = new Node(k);
        ++size_;
        return;
    }
    while(node != nullptr)
    {
        prev_node = node;
        if(k < node->key)
        {
            node = node->left;
            went_right = false;
        }
        else if (k > node->key)
        {
            node = node->right;
            went_right = true;
        }
        
        else
        {
            return;
        }
    }
    
    if(went_right)
    {
        prev_node->right= new Node(k, prev_node); // assigning the new node 
    }
    else
    {
        prev_node->left= new Node(k, prev_node);
    }
    ++size_;

    
    
}

template <typename T> 
void BST<T>::fix_height(Node* node)
{


}```

Upvotes: 1

Views: 844

Answers (1)

paddy
paddy

Reputation: 63471

The height of a node is defined as the maximum of its child nodes' heights plus 1.

Although your question title speaks of "post-order" (a term related to recursion), your code is not actually recursive. Normally, a post-order update happens after a recursive call.

Anyway, with your iterative solution the height can still be updated easily because you have stored parent pointers in your tree nodes. And so all you need to do is walk back through each node and update the height.

template <typename T> 
void BST<T>::fix_height(Node* node)
{
    while (node)
    {
        node->height = 1 + std::max(
            node->left ? node->left->height : -1,
            node->right ? node->right->height : -1);
        node = node->parent;
    }
}

It should be noted that your tree heights appear to treat a leaf node's height (that is, the height of a node that has no children) as 0. In order to make your fix_height function well-behaved even if called on a leaf node, then the height of "no child" is treated as -1.

If you decide that a leaf node's height should actually be 1, then you should change those "no child" heights to 0, and change the default height of a new node to 1.

To use this, you would call fix_height(prev_node); just before returning from your insert function.

Upvotes: 1

Related Questions