Inorder of BT.

This is a discussion on Inorder of BT. within the C# Programming forums, part of the General Programming Boards category; Hi, I am having a hard time following the steps of the following recursion: Code: void inorder(Node * node) { ...

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    122

    Inorder of BT.

    Hi,
    I am having a hard time following the steps of the following recursion:
    Code:
    void inorder(Node * node) {
    	if (node==NULL)
    		return;
    	inorder(node->left);
    	printf("%d ",node->data);
    	inorder(node->right);
    }
    Could anyone kindly explain this to me? For instance, why would 12 be printed right after 9 (please see attachment for data)?
    Attached Images Attached Images  

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    Well you've got three choices.


    // action
    doLeft()
    doRight()



    doLeft()
    // action
    doRight()



    doLeft()
    doRight()
    // action


    Why not compare all three (pre-order, in-order and post-order) all at the same time?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    I have. The recursion itself, the way it is processed, is giving me a hard time!
    For instance, how would the program get to 12 after 9? 9->left is passed, it is NULL, then what happens? I have debugged it and still couldn't figure out the "leap" to 12.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    Well there is no way down from 9, so the only way left is back up from where you came (ie, 12)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    Quote Originally Posted by peripatein View Post
    I have. The recursion itself, the way it is processed, is giving me a hard time!
    For instance, how would the program get to 12 after 9? 9->left is passed, it is NULL, then what happens? I have debugged it and still couldn't figure out the "leap" to 12.
    It's not a leap, it's a return.

    You start out at node 50, traverse left sequentially to nodes 17, 12, and 9.

    9 has no left node, so it prints 9 and checks its right node. 9 has no right node so the function returns.

    Now you're one level up the call stack, having just finished 12 left. The next thing that happens is to print 12 and then do 12 right.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recriating a bst tree from inorder
    By cfan in forum C Programming
    Replies: 5
    Last Post: 08-06-2009, 02:15 AM
  2. inorder traversal funtion
    By timmy123 in forum C++ Programming
    Replies: 2
    Last Post: 04-20-2009, 06:08 AM
  3. Print numbers by inorder..
    By NightWalker in forum C Programming
    Replies: 5
    Last Post: 09-15-2003, 10:24 AM
  4. Displaying tree thru inorder
    By Lord CyKill in forum C Programming
    Replies: 2
    Last Post: 04-12-2003, 10:23 AM
  5. InOrder traversal : show tree
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-17-2001, 09:38 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21