Create special binary search tree using C++

Question

I want to create a Binary search tree which has special Nodes. There should be three classes of Nodes, Internal Node, External Node and Root node, each inheriting a common parent Node and each type of node will have some unique function. Is it possible to create such a BST. The problem I am facing is suppose the first node I insert into the tree becomes the root node. The next node I insert will become External Node. Now if I insert another node then the external node has to become a internal node and the new node will become the external node. Also I cannot find a way to navigate through the tree from one node to another as the nodes will be of different types. Can a tree of this type be created. If yes then give me some suggestions of how this can be done.

Answer 1

If I understand correctly, you're worried about how objects in one class - External - need to become objects of another class - Internal. This, when C++ is a statically-typed language: Types (including the classes of objects) are determined at compile-time. Right?

Well, you can achieve this in at least one of two ways:

1. When an External node becomes Internal, delete the External node and replace it with an Internal node, properly initialized (e.g. to point at the new External node).
2. Give up on External and Internal being discrete types, and just check for children and parents to determine the node type dynamically.

Some more relevant reading material on these matters:

• (Programming language) type systems in this Wikipedia page.
• This SO question: What is duck typing?
• The Circle-vs-Eclipse problem, and specifically the desire to stretch circles into ellipses.

Answer 2

You could use basic inheritance some type enum and recursive calls. This could be a starting point:

enum NodeType
{
    eRoot,
    eInternal,
    eExternal
};

class BinaryNode
{
public:
   virtual NodeType GetType() = 0;
   virtual void UpdateTree() = 0;

protected:
   BinaryNode* ChildLeft;
   BinaryNode* ChildRight;
   BinaryNode* Parent;
};

class ExternalNode : public BinaryNode 
{
   NodeType GetType() override { return eExternal; }
   void UpdateTree() override 
   { 
      //... Replace node instances here(e.g. delete this node and construct the correct new one given this sub tree. call new InternalNode(this) for example) 
      // Call this towards the parent node so the tree will be transformed accordingly
   }
}
class InternalNode : public BinaryNode 
{ 
   NodeType GetType() override { return eInternal; }
   void UpdateTree() override { //... }
}
class RootNode : public BinaryNode 
{ 
   NodeType GetType() override { return eRoot; }
   void UpdateTree() override { //... }
}

This is just to give you an idea where to start. You can check the node type at runtime via GetType() and do some checks based on that.

Be aware that this kind of transformation is not particularly fast. If you want this to be fast, don't use different types and virtual function calls and pointers.

Place your binary tree inside an array and use binary indexing, so at a given index "n" use 2*n+1 to get the left child and 2*n+2 to get the right child. Then use some flags (root, external, internal etc.) to determine which functions you want to call on the binary node. I wouldn't use inheritance like in my code example to be fast or more readable. In fact, deciding externally what functions to call on a node can be much more readable and less error-prone.