How exactly is the print statement working in these two methods?

Question

This is wrt to Binary Search Tree.I am traversing the tree in 2 ways.1)InOrder Traversal An inorder traversal of tree t is a recursive algorithm that follows the the left subtree; once there are no more left subtrees to process, we process the right subtree. The elements are processed in left-root-right order. 2)PostOrder Traversal A postorder traversal of tree t is a recursive algorithm that follows the the left and right subtrees before processing the root element. The elements are processed left-right-root order.

I am confused over how the recursion methods and print statements are working. Could you please enlighten me?

static void inOrder(Leaf root){
    if(root != null){
        inOrder(root.left);
        System.out.print(root.value+" ");
        inOrder(root.right);
    }
}
static void postOrder(Leaf root){
    if(root != null){
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value+" ");
    }
}

What exactly is problem with it? Hint: The best way would be to draw some trees on a sheet of paper and travers them by hand. — Kevin Wallis
Also you can try implementing the iterative code. It will give you an good idea about how the recursion stack works. — Rudrani Angira

theJack theJack · Accepted Answer · 2016-07-19T16:58:09

The way this works is each function will print out a single, long line containing each of the values if the tree. As each of the algorithms goes through the tree, it appends the current value of the node to the output along with a space. For example, if we consider the following tree:

  2
 / \
1   3

The first algorithm will start at the 2, then call itself on the left child, 1. The function will then call itself on the left child, which is null, so it will return immediately. The function will then print "1 " to the console. The function will call itself on the right child, which is null, so it will return immediately. The function will then return to the 2, and "2 " will be printed to the console. The function will then call itself on the right child, which is the 3. The function will call itself on the left child , which returns, then print "3 " to the console, then call itself on the right child, which returns. The function will then return to the 2, and that will return to whatever called it. The console at the end will say

1 2 3

A similar thing would happen for the second algorithm, except the function would go to and print the left and right children, 1 and 3, respectively, before printing the root node, 2, resulting in the following output:

1 3 2

If you are having trouble understanding it, it would benefit you to draw yourself a tree and follow the code step by step to see what the computer is doing.

How exactly is the print statement working in these two methods?

2 Answers