Difficulty setting up threaded BST in C++

Question

I'm having trouble implementing a threaded Binary Search Tree in C++. I have a non-threaded tree completely implemented (see below code). What I'm having difficulty with is setting the threads to point to the correct parent node (without having an explicit parent pointer). (I have two functions - print() and printInOrder() that both work fine for a non-threaded binary tree that I need to work for a threaded one.)

My trouble is in the inserthelp() function. I can't figure out how to set the threads correctly. I have looked at countless sites and tried what feels like everything but the right answer. I've tried using an array to keep track of previous nodes visited and using that to determine the proper left and right threads, but just couldn't get it to work right. I need the constructor and setLeft/setRight functions in BSTNode class to correctly assign threads when applicable and set isLeft/RightThreaded accordingly, and then the printHelp and printInOrder functions of class BST to use whether the nodes are threaded to traverse the tree.

A few points:

I want to avoid recursion in printInOrder and print if at all possible. I'm aiming for a while loop that covers the whole tree.
I don't want to store an explicit parent node pointer anywhere.
I don't want to use a stack structure or any list of nodes to help in the printInOrder function. I want that to rely only on the current node and the nodes to which it points.

Here is a minimal (I think) reproducible example of what I have for a non-threaded tree:

using namespace std;

#include <iostream>
#include <stack> // want to avoid needing this
#include <string>

template <typename E>
class BinNode {};

template <typename Key, typename E>
class BSTNode : public BinNode<E> {
 public:
  E it;
  BSTNode* lp;
  BSTNode* rp;
  bool isLpChildPointer;
  bool isRpChildPointer;
  bool isLeftThreaded;
  bool isRightThreaded;
  Key k;
  BSTNode() { lp = rp = NULL; }
  BSTNode(Key K, E e, BSTNode* l, BSTNode* r) {
    k = K;
    it = e;
    lp = l;
    rp = r;
    isLpChildPointer = false;
    isRpChildPointer = false;
    isLeftThreaded = true;
    isRightThreaded = true;
  }
  void setLeft(BinNode<E>* b) {
    lp = (BSTNode*)b;
    isLpChildPointer = true;
    isLeftThreaded = false;
  }

  void setRight(BinNode<E>* b) {
    rp = (BSTNode*)b;
    isRpChildPointer = true;
    isRightThreaded = false;
  }
};

template <typename Key, typename E>
class BST {
 public:
  BSTNode<Key, E>* root;
  int nodecount;

  BSTNode<Key, E>* inserthelp(BSTNode<Key, E>*, const Key&, const E&,
                              BSTNode<Key, E>*[], int, int);
  void printhelp(BSTNode<Key, E>* root, int level) const {
    if (root == NULL) return;
    printhelp(root->lp, level + 1);
    for (int i = 0; i < level; i++) cout << "  ";
    cout << root->k << "\n";
    printhelp(root->rp, level + 1);
  }

  BST() {
    root = NULL;
    nodecount = 0;
  }

  void printInOrder() {
    std::stack<BSTNode<Key, E>*> stack; // how to get rid of stack here and only use while // loop, using only lp and rp to access all nodes
    BSTNode<Key, E>* current = root;
    while (current != nullptr || !stack.empty()) {
      while (current != nullptr) {
        stack.push(current);
        current = current->lp;
      }
      current = stack.top();
      cout << current->it << endl;
      stack.pop();
      current = current->rp;
    }
  }

  void insert(const Key& k, const E& e) {
    root = inserthelp(k, e, root);
    nodecount++;
  }

  BSTNode<Key, E>* inserthelp(const Key& k, const E& e, BSTNode<Key, E>* node) {
    if (node == nullptr) {
      return new BSTNode<Key, E>(k, e, NULL, NULL); // what to put here instead of NULL. 
                                                    // and how to keep track of what higher level nodes this new node should thread to.
    } else {
      if (k < node->k) {
        node->setLeft(inserthelp(k, e, node->lp));
      } else {
        node->setRight(inserthelp(k, e, node->rp));
      }
      return node;
    }
  }
  void print() const { printhelp(root, 0); }
};

int main() {
  BST<int, string> tree;

  tree.insert(77, "seventy-seven");
  tree.insert(70, "seventy");
  tree.insert(75, "seventy-five");
  tree.insert(66, "sixty-six");
  // other inserts...
  tree.insert(83, "eighty-three");
  tree.insert(87, "eighty-seven");
  tree.insert(65, "sixty-five");

  tree.print();
  tree.printInOrder();
}

Again, the above code works fine for a non-threaded tree - no problems whatsoever - does exactly what I want it to do. But I need it to work for a threaded tree. I worked on this issue for the better part of four or five hours earlier and then just couldn't look at it anymore.

I forgot these things even existed. I'm looking at the code. No #include <thread>. No pthreads, no CreateThread calls, and I'm thinking, "What? Asker post the working, non-threaded version? That's dumb." Nope. Mesa the dummy. — user4581301
– user4581301, Commented Apr 12 at 4:10
Again, the above code works fine -- no problems whatsoever -- Except it has a ton of memory leaks and is not safely copyable or assignable. I wished that C++ programmers didn't treat memory cleanup and simple object safety as an afterthought. — PaulMcKenzie
– PaulMcKenzie, Commented Apr 12 at 4:55
@user4581301 initially I also thought "threaded" was related to [multi-threading](en.wikipedia.org/wiki/Multithreading_(computer_architecture). So I editted and added a link to the relevant meaning of threaded binary tree. — wohlstad
– wohlstad, Commented Apr 12 at 6:33
Regarding the memory leaks mentioned above, using smart pointers instead of raw ones (so no raw new/delete) - can help a lot. — wohlstad
– wohlstad, Commented Apr 12 at 7:19

trincot · Accepted Answer · 2025-04-12 12:46:56Z

Threading -- in the sense of reusing pointers in a binary tree to allow for a traversal with O(1) space complexity -- is based on the following observation:

Null pointers could be overwritten with a pointer to some ancestor node: if used carefully, there is no loss of information here, as the said pointer can be reset to null after the traversal has proceeded beyond that point.

However, you cannot expect to just overwrite any pointer, as you will not have the capacity to restore that pointer to its original value unless you have O(𝑛) memory for that purpose, which is what you seem to want to avoid.

So the design you have with isLpChildPointer and isLeftThreaded is not the way to go:

It means you allocate a few booleans per node, so actually requiring O(𝑛) additional memory.
It does not allow to restore the original lp field once the algorithm decides to "unthread" the pointer so that the tree's shape is restored.

To apply the principle of threading with O(1) memory requirements, you can use what is called Morris traversal. An explanation can be found at many places, also on Stack Overflow: Explain Morris inorder tree traversal without using stacks or recursion.

Not related, but I would really promote the use of descriptive names, so which in many cases are longer than just one or two letters. With that also in mind, your code related to printInOrder could be modified to look like this:

#include <iostream>
#include <string>

template <typename E>
class BinNode {};

template <typename Key, typename E>
class BSTNode : public BinNode<E> {
public:
    E data;
    Key key;
    BSTNode* left = nullptr;
    BSTNode* right = nullptr;

    BSTNode(Key key, E data) : key(key), data(data) {}
    
    void print(int level) {
        std::cout << std::string(level * 2, ' ') << key << "\n";
    }
    
    BSTNode<Key, E>* findPredecessor() {
        if (!left) {
            return nullptr;
        }
        BSTNode<Key, E>* predecessor = left;
        while (predecessor->right && predecessor->right != this) {
            predecessor = predecessor->right;
        }
        return predecessor;
    }
};

template <typename Key, typename E>
class BST {
public:
    BSTNode<Key, E>* root = nullptr;
    int nodecount = 0;
  
    BSTNode<Key, E>* inserthelp(BSTNode<Key, E>*, const Key&, const E&,
                                BSTNode<Key, E>*[], int, int);
    
    void printInOrder() {
        BSTNode<Key, E>* current = root;
        
        while (current) {
            BSTNode<Key, E>* predecessor = current->findPredecessor();
            if (!predecessor) {
                current->print(0);
                current = current->right;
            } else if (!predecessor->right) {
                predecessor->right = current; // create thread
                current = current->left;
            } else {
                predecessor->right = nullptr;
                current->print(0);
                current = current->right;
            }
        }
    }
  
    void insert(const Key& key, const E& data) {
        root = inserthelp(key, data, root);
        nodecount++;
    }

    BSTNode<Key, E>* inserthelp(const Key& key, const E& data, BSTNode<Key, E>* node) {
        if (!node) {
            node = new BSTNode<Key, E>(key, data);
        } else if (key < node->key) {
            node->left = inserthelp(key, data, node->left);
        } else {
            node->right = inserthelp(key, data, node->right);
        }
        return node;
    }
    
    void print() const {
        printhelp(root, 0);
    }
};

int main() {
    BST<int, std::string> tree;
  
    tree.insert(77, "seventy-seven");
    tree.insert(70, "seventy");
    tree.insert(75, "seventy-five");
    tree.insert(66, "sixty-six");
    // other inserts...
    tree.insert(83, "eighty-three");
    tree.insert(87, "eighty-seven");
    tree.insert(65, "sixty-five");
  
    tree.printInOrder();
}

For printing with indentation, this will not work, as the threads make back-jumps potentially skipping multiple levels. To somehow retain this information, O(𝑛) auxiliary memory is needed. For instance, we could have some temporary field in each node (that is a target of a thread) to retain its level for printing purposes.

Here is the update of the above code to implement that:

#include <iostream>
#include <string>

template <typename E>
class BinNode {};

template <typename Key, typename E>
class BSTNode : public BinNode<E> {
public:
    E data;
    Key key;
    BSTNode* left = nullptr;
    BSTNode* right = nullptr;
    int tempLevel; // Used for temporarily saving and restoring a node's level.

    BSTNode(Key key, E data) : key(key), data(data) {}
    
    void print(int level) {
        std::cout << std::string(level * 2, ' ') << key << "\n";
    }
    
    BSTNode<Key, E>* findPredecessor() {
        if (!left) {
            return nullptr;
        }
        BSTNode<Key, E>* predecessor = left;
        while (predecessor->right && predecessor->right != this) {
            predecessor = predecessor->right;
        }
        return predecessor;
    }
};

template <typename Key, typename E>
class BST {
public:
    BSTNode<Key, E>* root = nullptr;
    int nodecount = 0;
  
    BSTNode<Key, E>* inserthelp(BSTNode<Key, E>*, const Key&, const E&,
                                BSTNode<Key, E>*[], int, int);
    
    void printInOrder() {
        BSTNode<Key, E>* current = root;
        
        int level = 0;

        while (current) {
            BSTNode<Key, E>* predecessor = current->findPredecessor();
            if (!predecessor) {
                current->print(level);
                current = current->right;
            } else if (!predecessor->right) {
                current->tempLevel = level; // save level for when returning here via thread
                predecessor->right = current; // create thread
                current = current->left;
            } else {
                predecessor->right = nullptr;
                level = current->tempLevel; // restore level as we returned here via thread
                current->print(level);
                current = current->right;
            }
            level++;
        }
    }
  
    void insert(const Key& key, const E& data) {
        root = inserthelp(key, data, root);
        nodecount++;
    }

    BSTNode<Key, E>* inserthelp(const Key& key, const E& data, BSTNode<Key, E>* node) {
        if (!node) {
            node = new BSTNode<Key, E>(key, data);
        } else if (key < node->key) {
            node->left = inserthelp(key, data, node->left);
        } else {
            node->right = inserthelp(key, data, node->right);
        }
        return node;
    }
    
    void print() const {
        printhelp(root, 0);
    }
};

int main() {
    BST<int, std::string> tree;
  
    tree.insert(77, "seventy-seven");
    tree.insert(70, "seventy");
    tree.insert(75, "seventy-five");
    tree.insert(66, "sixty-six");
    // other inserts...
    tree.insert(83, "eighty-three");
    tree.insert(87, "eighty-seven");
    tree.insert(65, "sixty-five");
  
    tree.printInOrder();
}

Collectives™ on Stack Overflow

Difficulty setting up threaded BST in C++

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related