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

$\endgroup$
  • $\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 '15 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 '15 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 '15 at 0:02
  • $\begingroup$ @user3467349 Alright thanks, I understand it now! $\endgroup$ – Ken Mar 22 '15 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 '15 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.