<commit_before>/*
 * in-order.cpp
 * Copyright (C) 2014 KuoE0 <<EMAIL>>
 *
 * Distributed under terms of the MIT license.
 */

#include <iostream>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left, *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* insertNode(TreeNode* now, const int val) {
	if (!now) now = new TreeNode(val);
	else if (val < now->val) now->left = insertNode(now->left, val);
	else now->right = insertNode(now->right, val);
	return now;
}

void recursivePostOrderTraversal(TreeNode* now) {
	if (now) {
		recursivePostOrderTraversal(now->left);
		recursivePostOrderTraversal(now->right);
		cout << now->val << ' ';
	}
}

void morrisPostOrderTraversal(TreeNode* now) {
}

int main() {
	int n, x;
	while (cin >> n) {
		TreeNode *root = NULL;
		for (int i = 0; i < n; ++i) {
			cin >> x;
			root = insertNode(root, x);
		}
#ifdef RECURSIVE_METHOD
		recursivePostOrderTraversal(root);
		cout << endl;
#endif
#ifdef MORRIS_METHOD
		morrisPostOrderTraversal(root);
		cout << endl;
#endif
	}

	return 0;
}


<commit_msg>add morris traversal in constant space<commit_after>/*
 * in-order.cpp
 * Copyright (C) 2014 KuoE0 <<EMAIL>>
 *
 * Distributed under terms of the MIT license.
 */

#include <iostream>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left, *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* insertNode(TreeNode* now, const int val) {
	if (!now) now = new TreeNode(val);
	else if (val < now->val) now->left = insertNode(now->left, val);
	else now->right = insertNode(now->right, val);
	return now;
}

void recursivePostOrderTraversal(TreeNode* now) {
	if (now) {
		recursivePostOrderTraversal(now->left);
		recursivePostOrderTraversal(now->right);
		cout << now->val << ' ';
	}
}

void morrisPostOrderTraversal(TreeNode* now) {

	TreeNode *dummy = new TreeNode(0), *cur, *tmp;
	function<TreeNode* (TreeNode*, TreeNode*)> rightmost_self = [&] (TreeNode* now, TreeNode* target) { 
		// right child is target or empty
		if (now->right == target || !now->right) return now;
		// find rightmost recursively
		return rightmost_self(now->right, target);
	};
	function<void (TreeNode*)> output_path = [&] (TreeNode* now) {
		if (now->right) output_path(now->right);
		// output in reversed order
		cout << now->val << ' ';
	};

	// dummy node, make the root has no right child
	dummy->left = now;
	cur = dummy;

	while (cur) {

		// reach the leftmost node
		if (!cur->left) {
			cur = cur->right;
			continue;
		}

		// find the rightmost node at left child and that node is not self
		tmp = rightmost_self(cur->left, cur);

		if (tmp->right == cur) {
			// unlink the thread
			tmp->right = NULL;
			// output the value in reverse order
			output_path(cur->left);
			cur = cur->right;
		}
		else {
			// link to self
			tmp->right = cur;
			cur = cur->left;
		}
	}
}

int main() {
	int n, x;
	while (cin >> n) {
		TreeNode *root = NULL;
		for (int i = 0; i < n; ++i) {
			cin >> x;
			root = insertNode(root, x);
		}
#ifdef RECURSIVE_METHOD
		recursivePostOrderTraversal(root);
		cout << endl;
#endif
#ifdef MORRIS_METHOD
		morrisPostOrderTraversal(root);
		cout << endl;
#endif
	}

	return 0;
}



{'fraction_non_alphanumeric': 0.1535334584115072, 'fraction_numerical': 0.004690431519699813, 'mean_word_length': 3.6429608127721336, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 51, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7144685', 'n_tokens_mistral': 1275, 'n_tokens_neox': 1163, 'n_words': 324}