In order traversal binary tree

Question

I am learning java. I saw this code somewhere. Does the following code traverse it correctly? Is result list being called correctly? Will it append properly?

public void traverse(Node<T> input, List<T> resultlist) {
   if (input != null) {
      traverse(input.getLeftNode(), resultlist)

      resultlist.add(input.getValue())

      traverse(input.getRightNode(), resultlist)
   }
}

On the middle line, I think `result` should be `resultlist`. — nvioli, Nov 18 '16 at 18:23
Possible duplicate of [In-order iterator for binary tree](http://stackoverflow.com/questions/12850889/in-order-iterator-for-binary-tree) — rbucinell, Nov 18 '16 at 18:23

score 1 · Accepted Answer · answered Nov 18 '16 at 18:44

By asking whether it does do an in-order traversal (does this do what it is supposed to do), I'm guessing you just don't understand the difference between the traversals...

Primer:

In order to truly understand this, you need to understand an important aspect of data structures: recursion. This is something that you need to grasp. It may take a bit, and after trying different exercises..it will just click.

Here is a resource for this to get started:

http://www.programmerinterview.com/index.php/recursion/explanation-of-recursion/

Now coming to your question of tree traversal, the typical convention is as follows:

Pre-Order:

traversalFunction(Node)
   doStuffWithNode(Node)   //prechild traversal
   traversalFunction(Node.left)
   traversalFunction(Node.right)

In-Order

traversalFunction(Node)
   traversalFunction(Node.left)
   doStuffWithNode(Node)   //within child traversal
   traversalFunction(Node.right)

Post-Order:

traversalFunction(Node)
   traversalFunction(Node.left)
   traversalFunction(Node.right)
   doStuffWithNode(Node)  //post child traversal

So to answer your question...if you have the method that performs an action on the node in between the left and right traversals then yes it is an in-order traversal. That is what you are doing.

You can find more information on the traversals here: https://en.wikipedia.org/wiki/Tree_traversal

Now as to the correctness of the rest of your code, I am unsure because you really haven't inputted any information on your Node class or anything.

In order traversal binary tree

1 Answers1