CODEWITHSUNDEEP
crecursionbinary-search-treetraversal
Budding_Programmer
Budding_Programmer

Reputation: 15

How does recursion work on traversing through a binary tree, and counting the number of list nodes?

I have trouble visualizing these following print and size functions from the following URL (https://repl.it/@flowerplowedup/SquigglyVerifiablePaint#main.c):

Upvotes: 0

Views: 90

Answers (1)

John Bode
John Bode

Reputation: 123558

Let's suppose you enter the input sequence

4 8 2 7 9 1 3 -1

You wind up with a tree that looks like this:

                           4
                          / \
                         /   \
                        2     8
                       / \   / \
                      1   3 7   9

print_ascending's execution will look something like this :

print_ascending( node(4) )
{
  node(4) != NULL
  print_ascending( node(4)->left == node(2) )
  {
    node(2) != NULL
    print_ascending( node(2)->left == node(1) )
    {
      node(1) != NULL
      print_ascending( node(1)->left == NULL )
      {
        NULL == NULL
        return
      }
      print( 1 )
      print_ascending( node(1)->right == NULL)
      {
        NULL == NULL
        return
      }
      return
    }
    print( 2 )
    print_ascending( node(2)->right == node(3))
    {
      node(3) != NULL
      print_ascending( node(3)->left == NULL )
      {
        NULL = NULL
        return
      }
      print( 3 )
      print_ascending( node(3)->right == NULL )
      {
        NULL = NULL
        return
      }
    }
    print( 4 )
    print_ascending( node(4)->right == node(8) )
    {
      node(8) != NULL
      print_ascending( node(8)->left == node(7) )
      {
        node(7) != NULL
        print_ascending( node(7)->left == NULL )
        {
          NULL == NULL
          return
        }
        print( 7 )
        print_ascending( node(7)->right == NULL )
        {
          NULL == NULL
          return
        }
        return
      }
      print( 8 )
      print_ascending( node(8)->right == node(9) )
      {
        node(9) != NULL 
        print_ascending( node(9)->left == NULL )
        {
          NULL == NULL
          return
        }
        print( 9 )
        print_ascending( node(9)->right == NULL )
        {
          NULL == NULL
          return
        }
        return
      }
      return
    }
    return
  }
  return
}
return

Hopefully that helps visualize what's going on, and what's going on in the size function as well. Recursion's one of those concepts that takes a while to wrap your head around.

Upvotes: 1

Related Questions