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:
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.
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:
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();
}