Clarification over In-Order traversal in binary search tree

Question

I'm studying Trees in Java, and came across some confusing lines in the book I'm studying. The diagram given for the in-order traversal is this:

The code for the traversal (recursive) is:

private void inOrder(Node leftRoot) {
    if (localRoot != null) {
        inOrder(localRoot.leftChild);
        System.out.println(localRoot.iData + " ");
        inOrder(localRoot.rightChild);
    }
 }

The lines I'm confused at are:

Now we’re back to inOrder(A), just returning from traversing A’s left child. We visit A and then call inOrder() again with C as an argument, creating inOrder(C). Like inOrder(B), inOrder(C) has no children, so step 1 returns with no action, step 2 visits C, and step 3 returns with no action. inOrder(B) now returns to inOrder(A).

However, inOrder(A) is now done, so it returns and the entire traversal is complete. The order in which the nodes were visited is A, B, C; they have been visited inorder. In a binary search tree this would be the order of ascending keys.

I've highlighted the parts where I'm stuck at. First, I think in the third step, inOrder(C)[and not inOrder(B)] returns to inOrder(A).And second, the order in which the nodes were visited should be B -> A -> C.

Please help me out!

Since the System.out.println(localRoot.iData + " "); is in the second row, this print out(or visit) order should be B->A->C. But the real access order it A->B->C. — Roger Dwan
@Shloim it's Robert Lafore's Data Structures and Algorithms as I mention in my answer below. A fairly good book for beginners, but I do remember being frustrated there were no published errata when I was learning from it. — The111
It's the book Data Structures & Algorithms in Java - Robert Lafore — Manish Giri
I'll just recommend this one, and let you go on your way. mitpress.mit.edu/books/introduction-algorithms — Shloim

The111 The111 · Accepted Answer · 2015-11-25T08:25:52

Yes, you are correct on both counts. These seem to be typos, or errata.

As a sidenote, I recognized the diagram style in your post because I learned data structures years ago from the same book (Lafore). Unfortunately it does not seem that he has a list of errata published anywhere, which is disappointing, since most authors do strive to do this.

Clarification over In-Order traversal in binary search tree

1 Answers