Giudoku Official Site
In-order visit of a tree
For now, I will present only the recursive version of this function: the iterative version is not ready yet (it's a bit more complicated and needs some further explainings)!
The input is a randomly generated binary search tree. This tree has the following property: the left son of each node can contain only a key lesser than the node's key, while the right one contains only keys greater than or equals to the node's key.
The in order visit is a method for visiting each node. Let's take a "family" (a node with its sons): the function first reads the left node's key, then the parent's key, and then the right key. Repeating this for each "family" in the tree, the printed integers are in order.

The algorithm is quite easy: until the pointer is not null (we reached a leaf), it calls itself on the left subtree (which has the current left son as root), then it prints out the parent's key, and then calls itself on the right subtree. In this way, the order is always maintained.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>

struct _Node_s {
	int key;
	struct _Node_s *parent;
	struct _Node_s *left;
	struct _Node_s *right;
};

typedef struct _Node_s Node;
typedef struct _Node_s *Tree;

Node *getNewNode(int key)
{
	Node *ptr = (Node *) malloc(sizeof(Node));

	if (ptr != NULL) {
		memset(ptr, 0, sizeof(Node));
		ptr->key = key;
	}

	return ptr;
}

void deleteTree(Tree ptr)
{
	if (ptr != NULL) {
		deleteTree(ptr->left);
		deleteTree(ptr->right);
		free(ptr);
	}
}

int addNode(Tree *ptr, int key)
{
	Node *node = getNewNode(key);
	Node *prec = NULL;
	Node *curr = (*ptr);

	/*
	 * Check if the allocation failed or not.
	 */
	if (node == NULL) {
		return -1;
	}

	/*
	 * Find the correct position for the new node.
	 */
	while (curr != NULL) {
		prec = curr;
		curr = (key < curr->key) ? curr->left : curr->right;
	}

	if (prec == NULL)
	{
		(*ptr) = node;
	}
	else
	{
		node->parent = prec;

		if (key < prec->key)
		{
			prec->left = node;
		}
		else
		{
			prec->right = node;
		}
	}

	return 0;
}

void In_Order(Tree p)
{
	if (p == NULL)
	{
		return;
	}

	In_Order(p->left);
	printf("%d ", p->key);
	In_Order(p->right);
}

int main()
{
	Tree ptr = NULL;
	int i = 0;

	srand(time(NULL));

	/*
	 * Create a new binary search tree with 10 random nodes.
	 */
	while (i < 10) {
		int key = 1 + rand() % 1000;

		if (addNode(&ptr, key) != 0) {
			fprintf(stderr, " [**] Allocation failed! Exiting.\n");
			deleteTree(ptr);
			return -1;
		}
		i++;
	}

	In_Order(ptr);
	deleteTree(ptr);
	return 0;
}