How does this binary tree traversal algorithm work?

Question

So I'm given the algorithm

void traverse(Node node) {
    if (node != null) {
        traverse(node.leftChild);
        System.out.println(node.name);
        traverse(node.rightChild);
    }
}

I don't understand how this works. So if I'm at a point where the input is null, what happens? Assuming that we print the null node's parent (I don't know how you get there) and continue on, let's say we've covered nodes deep into a tree, how do we climb back up the tree? Where in this algorithm can we continuously jump to parent nodes as needed?

Answer 1

To understand this you need to understand recursion first. Here for every node as parent we do same thing for left child then for the right child. and print the parent name after traverse left side.

When node is null we don't do anything, so no child is called

void traverse(Node node) {
    if(node!=null) {
        traverse(node.leftChild);
        System.out.println(node.name);
        traverse(node.rightChild);
    }
}

Example:

parent and childs
1 -> 2,3
2 -> 4,5
3 -> 6,7

So here traverse(1) called as root first.

traverse(1) -> traverse(2) // left
               traverse(3) // right

traverse(2) -> traverse(4) // left
               traverse(5) // right

traverse(3) -> traverse(6) // left
               traverse(7) // right

traverse(4) -> nothing called
traverse(5) -> nothing called
traverse(6) -> nothing called
traverse(7) -> nothing called

Now exact the order it called

traverse(1) -> traverse(2) // left
                  traverse(2) -> traverse(4) // left
                                     traverse(4) -> nothing called
                                 traverse(5) // right
                                     traverse(5) -> nothing called
               traverse(3) // right
                  traverse(3) -> traverse(6) // left
                                      traverse(6) -> nothing called
                                 traverse(7) // right
                                      traverse(7) -> nothing called