binary tree traversal code explaination needed

Question

I have a question on how this binary tree traversal code works.

void BinaryTree_Functions::preorder(Binary_TreeNode* bt)
    {
        if (bt == NULL) { return; }
        cout <<  bt->data <<endl;
        preorder(bt->Left);
        preorder(bt->Right);
    }

preorder traversal

    void BinaryTree_Functions::inorder(Binary_TreeNode* bt)
    {
        if (bt == NULL) { return; }
        inorder(bt->Left);
        cout << bt->data << endl;
        inorder(bt->Right);
    }

inorder traversal

    void BinaryTree_Functions::postorder(Binary_TreeNode* bt)
    {
        if (bt == NULL) { return; }
        postorder(bt->Left);
        postorder(bt->Right);
        cout << bt->data << endl;
    }

postorder traversal

I know how these traversals work but I did not understand the code.

Answer 1

It is dificult to explain when you don't say what specifically is confusing you. The issue seems to be recursion. To see more easily what happens you could use an example tree and see how the output differs. To see how the different orders traverse the three differently you can also look at this fake tree:

#include<iostream>
#include<string>

struct fake_tree {
    unsigned size = 4;
    void preorder(const std::string& node){
        if (node.size() >= size) return;
        std::cout << node << "\n";
        preorder(node+"l");
        preorder(node+"r");
    }
    void postorder(const std::string& node){
        if (node.size() >= size) return;
        postorder(node+"l");    
        postorder(node+"r");
        std::cout << node << "\n";
    }
    void inorder(const std::string& node){
        if (node.size() >= size) return;
        inorder(node+"l");
        std::cout << node << "\n";
        inorder(node+"r");
    }
};

int main()
{
    fake_tree ft;
    ft.preorder("0");
    std::cout << "\n";
    ft.postorder("0");
    std::cout << "\n";
    ft.inorder("0");
}

output is:

0
0l
0ll
0lr
0r
0rl
0rr

0ll
0lr
0l
0rl
0rr
0r
0

0ll
0l
0lr
0
0rl
0r
0rr

The output tells you directly where in the call stack the output is produced. For example the last 0rr is produced by inorder("0") calling inorder("0r") which in turn calls inorder("0rr"). Because inorder("0") first calls inorder("0l") then prints "0" and then calls inorder("0r"), thats the order you see in the output.

Similarly inorder("0r") first calls inorder("0rl") then prints "0r" then calls inorder("0rr").

If you now draw the tree on paper you can track how the different traversals go through the tree in different ways.