#ifndef HELLOCPLUS_TREE_TEST_H
#define HELLOCPLUS_TREE_TEST_H

struct TreeNode {
    int value;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(int x) : value(x), leftChild(NULL), rightChild(NULL) {}
};

TreeNode *getTree(int length);

void *inorderTraversal(TreeNode *root);

#endif //HELLOCPLUS_TREE_TEST_H

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "tree_test.h"

TreeNode *addNode(TreeNode *head, int value) {
    if (head == NULL) {
        head = (TreeNode *) malloc(sizeof(TreeNode));
        head->value = value;
        head->leftChild = NULL;
        head->rightChild = NULL;
    } else if (value >= head->value) {
        head->rightChild = addNode(head->rightChild, value);
    } else {
        head->leftChild = addNode(head->leftChild, value);
    }
}

TreeNode *getTree(int length) {
    srand((unsigned) time(NULL));
    TreeNode *head = NULL;
    TreeNode *p = NULL;
    for (int i = 0; i < length; i++) {
        if (head == NULL) {
            head = addNode(head, rand());
            p = head;
        } else {
            p = addNode(p, rand());
        }
    }
    return head;
}

void *inorderTraversal(TreeNode *root) {
    TreeNode *cur = root;
    TreeNode *prev = NULL;
    TreeNode *head = NULL;

    while (cur != NULL) {
        if (cur->leftChild == NULL) {
            printf("%d ", cur->value);
            cur = cur->rightChild;
        } else {
            // find predecessor
            prev = cur->leftChild;
            while (prev->rightChild != NULL
                   && prev->rightChild != cur) {
                prev = prev->rightChild;
            }

            if (prev->rightChild == NULL) {
                prev->rightChild = cur;
                cur = cur->leftChild;
            } else {
                prev->rightChild = NULL;
                printf("%d ", cur->value);
                cur = cur->rightChild;
            }
        }
    }
}