Search code examples
javaalgorithmbinary-treebinary-search-tree

How to correct my inorder traversal of a binary tree?

So for the tree I'm working on, I can't figure out the Inorder Traversal. Currently I have:

4, 11, 9, 1, 5, 6, 7, 8, 3, 2, 10

but this is incorrect. If anyone has an explanation of the correct answer, that would be helpful! I watched some videos for it but I have no idea what went wrong.

enter image description here

I tried:

4, 11, 9, 1, 5, 6, 7, 8, 3, 2, 10

4, 11, 9, 1, 5, 6, 7, 8, 3, 10, 2

both of these are incorrect, I'm not sure what to do with the long strand on the left or the order.

Solution

  • The "leftmost" node will be first in the inorder traversal.

    One way to get a feel for this traversal order, is to draw the tree in such a way that every node ends up in its own, vertical column, such that below that node, that column is completely empty: no other nodes there, nor edges crossing that column. In other words, the nodes in a parent node's left sub tree should all be positioned more to the left than the parent node. Same thing for the nodes in its right sub tree: they should all be positioned more to the right.

    For your example tree, that leads to this representation:

    enter image description here

    And now all that you have to do is read the node labels from left to right:

    9 11 4 1 5 6 8 7 3 2 10