Morris Traversal / Deletion

morris.cpp

// see https://eopxd.com/2020/08/30/morris-traversal/ for explaination
#include <iostream>
#include <cassert>
#include <vector>
#include <memory>

using namespace std;

template<class T>
struct Tree {
	struct Node {
		T data;
		Node *left, *right;
		Node ( const T &value ) : data(value), left(nullptr), right(nullptr) {
			cout << "create node with value: " << value << "\n";
		}
		~Node () {
			cout << "delete node with value: " << data << "\n";
		}
	};
	Node *root;
	size_t size;
	Tree () : root(nullptr), size(0) {}
	void in_order () { // morris traversal
		Node *now = root, *tmp = nullptr;
		while ( now ) {
			if ( !now->left ) {
				cout << now->data << ", ";
				now = now->right;
			} else {
				tmp = now->left;
				while ( tmp->right and tmp->right != now ) {
					tmp = tmp->right;
				}
				if ( !tmp->right ) {
					tmp->right = now;
					now = now->left;
				} else {
					tmp->right = nullptr;
					cout << now->data << ", ";
					now = now->right;
				}
			}
		}
		cout << "\n";
	}
	~Tree () { // morris traversal deletion
		Node *now = root, *tmp = nullptr;
		while ( now ) {
			if ( !now->left ) {
				tmp = now;
				now = now->right;
				delete tmp;
			} else {
				tmp = now->left;
				while ( tmp->right and tmp->right != now ) {
					tmp = tmp->right;
				}
				if ( !tmp->right ) { // left-subtree visit
					tmp->right = now;
					tmp = now;
					now = now->left;
					tmp->left = nullptr;
				} else { // no repeating left visit
					assert(0);
				}
			}
		}
	}

	void insert ( T val ) {
		++size;
		if ( !root ) {
			root = new Node(val);
			return;
		}
		Node *now = root;
		while ( 1 ) {
			if ( val < now->data ) {
				if ( !now->left ) {
					//cout << "insert left\n";
					now->left = new Node(val);
					break;
				} else {
					now = now->left;
				}
			} else {
				if ( !now->right ) {
					//cout << "insert right\n";
					now->right = new Node(val);
					break;
				} else {
					now = now->right;
				}
			}
		}
	}
};

int main ()
{
	Tree<int> t;
	vector<int> seq = {6, 2, 7, 1, 3, 9, 5, 8, 4};
	for ( auto x : seq )
		t.insert(x);
	t.in_order();
	return (0);
}