Przechodzenie po drzewie BST w sposób in order

PrintInOrderPrivate(node *Ptr)
{
    if(root != NULL)
    {
        if(Ptr -> left != NULL )
        {
            PrintInOrderPrivate(Ptr -> left);
        }
        cout << Ptr -> key << " ";
        if(Ptr -> right != NULL)
        {
            PrintInOrderPrivate(Ptr -> right);
        }
    }
    else
    {
        cout << "Drzewo jest puste\n";
    }
} 

Idziemy po wartościach od najmniejszej do najmniejszej. Jak ten kod zadziała w przypadku, gdy liść nie ma żadnego węzła. Wtedy żaden warunek się nie wykona, a mimo to program wypisuje wszystkie elementy od najmniejszego do największego.

Chodzi o to, że jak przejdę najbardziej w lewo i ten liść już nie ma węzła ani w lewo ani w prawo to jak na podstawie tej funkcji on wraca do tego liścia wyżej co był w nim poprzednio?

Magia zwana rekurencją. Zauważ że jak kończy sie wykonanie funkcji to wracasz w miejsce z którego ja wywołałeś, w tym przypadku do "wyższego" wywołania tej funkcji.

Przechodzi się do lewego albo prawego wskaźnika:

 PrintInOrderPrivate(Ptr -> left)

. Tak to rozumiem. I ciągle tylko widzę jak rekurencją idziemy w dół drzewa.

No dobra, ale kiedy funkcja napotyka na return to wraca w miejsce z którego ja wywołałeś, prawda? Jak masz np.

int f(){
  return 1;
}

int f2(){
  f();
  //tutaj znajdziemy się kiedy funkcja f() sie skończy
}

No i teraz wyobraź sobie że te twoje wywołania rekurencyjne nie idą w nieskończoność! Warunkiem jest że istnieje coś po lewej albo prawej stronie. Jak zejdziesz na sam dół w lewo i dojdziesz do liścia to on już nie ma żadnych dzieci więc funkcja nie wywoła już żadnej kolejnej funkcji tylko wróci. I wróci gdzie? Tam skąd została wywołana czyli do wywołania funkcji na rzecz "rodzica" tego liscia z którego wróciliśmy!

Moja rada? Użyj debugera. Ma on tą własność że pokazuje ci stan stosu, tzn pokazuje ci skąd się znalazłeś w danym miejscu. Pokaże ci z która linijka której funkcji sprawiła że jesteś tam gdzie jesteś.