0
$\begingroup$

Edit: Solved, see comments

I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is:

sub P(TreeNode)
   If LeftPointer(TreeNode) != NULL Then
      P(TreeNode.LeftNode)
   Output(TreeNode.value)
   If RightPointer(TreeNode) != NULL Then
      P(TreeNode.RightNode)
end sub

If I've understood correctly, then the algorithm above, for the BST below, would first traverse to the node with element 5 and then output it. After that, it checks whether the right child of that node is NULL, which it is. Doesn't the algorithm stop there?

Or is the pseudo code above incomplete? I have looked at quite a few sites and they all give the same short code. If it is incomplete, what would I have to add to the pseudocode so that it walks through the whole tree?

enter image description here

Improve this question
$\endgroup$
6
  • $\begingroup$ It's a recursive algorithm. It may help if you write it out on paper as you go through the calls. $\endgroup$
    – user3467349
    Mar 21, 2015 at 23:53
  • $\begingroup$ @user3467349 I do understand that it is recursive, but I don't understand what would happen after it is at the node with element 5. To my understanding, it would Output(TreeNode.value) (which is 5 of course), and then it proceeds to check whether the right child of the node with element 5 is not NULL. If it is not NULL, it makes a recursive call again. However, it is NULL (because the node with element 5 doesn't have a right child), so what does the algorithm do then? $\endgroup$
    – Ken
    Mar 21, 2015 at 23:58
  • 1
    $\begingroup$ When an Node has no left or right nodes it will only output it's own value and return executing the rest of the calling function (in this case at the one P(20)). Remember execution does not end until the starting function returns (at P(90)). $\endgroup$
    – user3467349
    Mar 22, 2015 at 0:02
  • $\begingroup$ @user3467349 Alright thanks, I understand it now! $\endgroup$
    – Ken
    Mar 22, 2015 at 0:18
  • 3
    $\begingroup$ Feel free to write up an explanation and answer your own question, if you like (if you think it might be useful to others). And welcome to CS.SE! $\endgroup$
    – D.W. ♦
    Mar 22, 2015 at 6:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.