Rekurencyjne dodawanie kolejnych węzłów (drzewo binarne)

Mam jeszcze jeden problem i bardzo zależy mi na jego zrozumieniu. Chodzi o taką funkcję:

struct tnode *add_tree(struct tnode *p, int x) {

	if (!p) {
		p = (struct tnode *) malloc (sizeof(struct tnode));
		p->number = x;
		p->left = p->right = NULL;
	}

	else if (x<p->number) {
		add_tree(p->left, x);
	}
	else if (x>p->number) {
		add_tree(p->right, x);
	}

	return p;

}

I załóżmy, że w mainie mam coś takiego:

struct tnode *root;
	root = NULL;

	root = add_tree(root, 5);
	root = add_tree(root, 10);
	root = add_tree(root, 7);

Czyli uruchamiamy za pierwszym razem funkcję add_tree(). Jako że root (parametr p w funkcji) był równy NULL funkcja alokuje pamięć i przypisuje wartość 5 do p->number. Zwracamy adres do wspomnianego p. Uruchamiamy ją ponownie - tym razem p już istnieje, więc funkcja sprawdza, czy 10 jest większe od 5. Jest, więc uruchamiamy add_tree(p->right, 10) i znowu historia się powtarza - p->right było puste, więc tworzymy węzeł i dajemy tam 10.

Jest to jednak przecież wywołanie rekurencyjne. Na samym końcu funkcja add_tree() zawsze zwraca wskaźnik do struktury. Jeżeli jednak wcześniej wywoła się ponownie add_tree() to funkcja zacznie wykonywanie kodu od początku, a ta instrukcja return p zostanie wykonana później. Ale właśnie - kiedy? Nie do końca rozumiem tę rekurencję, a bardzo bym chciał :) W jakiej kolejności są potem zwracane te p? Bo wydawało mi się, że rekurencyjnie będzie to miało miejsce od końca - czyli od najbardziej głębokiego węzła do nadrzędnego. Ale wtedy to chyba nie ma sensu...

Sorry, że taki długi post. Mam nadzieję, że ktoś znajdzie chwilkę, żeby przeczytać. Chodzi mi o samo wytłumaczenie zasady działania tej funkcji.

Jak masz problem ze zrozumieniem rekurencji to zainstaluj sobie jakiś program do grafiki żółwia i porysuj sobie jakieś obrazki dane rekurencyjnym wzorem. Ogółem gdy masz wywołanie rekurencyjne to ta funkcja będzie się uruchamiać aż napotka nulla, wtedy alokuje, ustawia wartość i wychodzi do funkcji nadrzędnej (tej która ją wywołała), ta natomiast wraca do kolejnej nadrzędnej itd.

czyli

wywolanie 0
    wywolanie 1
         wywolanie 2
             (...)
                 wywolanie n
                 powrot do n - 1
            (...)
        powrot do 1
   powrot do 0
powrot do 'programu' (wyjscie z funkcji do programu)

to chciałeś wiedzieć? Może nie zrozumiałem problemu :)

Wielkie dzięki za odpowiedź. Też tak rozumiem rekurencję. Ale wydaje mi się, że w przypadku tej funkcji, jeżeli rekurencja będzie tak działała, to powstanie drzewo kompletnie niesymetryczne. Bo załóżmy, że najpierw mamy liczbę 5. Potem jest 10, która od 5 jest większe, więc "rozgałęzi" się w prawo. I nie wracamy już do nadrzędnego węzła, tylko zwracamy właśnie adres z tą 10-tką, przez to kolejna wartość (np 3) nie będzie po lewej stronie 10 (bo 3 jest mniejsze od 5), tylko powstanie 3 rząd z liczbą po lewej stronie od 10. Przez to zawsze jedna gałązka (lewa lub prawa) nie będzie istniała. Potem niby wracamy do tych funkcji nadrzędnych, ale jest już chyba za późno, żeby te gałęzie dorysować.

Choć w takim wypadku funkcja ta nie spełniałaby swojej roli, więc wnioskuje, że raczej moje rozumowanie jest błędne. Ale gdzie robie błąd?