Binary Trees — Tracing through code

Question

Given the binary tree shown below, determine the order in which the nodes of the binary tree shown below are visited assuming the function A(root) is invoked. Assume that the tree nodes and pointers are defined as shown. Assume that root is a pointer to the node containing 60. My answer to this problem is given below. Is it correct? What did I do wrong?

                                   60
                                 /    \
                                30     90
                               /  \   / 
                              5   38  77
                               \  /  / \
                               8 32 62  88



struct treeNode{
  int data;
  struct treeNode *left, *right:
  {

struct treeNode *tree_ptr;

void A(struct treeNode *node_ptr){
    if (node_ptr != NULL){
    printf(“%d ,”,node_ptr->data);
    B(node_ptr->left);
    B(node_ptr->right);
   }   
}

void B(struct treeNode *node_ptr){
    if (node_ptr != NULL) {
    A(node_ptr->left);
    printf(“%d ,”,node_ptr->data);
    A(node_ptr->right);
   }
 }   

Answer: In void A it says to first print node_ptr-> data so 60 gets printed Then the function calls B(node_ptr->left) then within B, A gets called (node_ptr->left) then you print that data which is 5. And then A(node_ptr->right) gets called go back up to A, print that data so 8 gets printed. Now Im not so sure what to do next but I get logically it would make sense to print 30 but Im not sure how the ptr gets from 8 to 30. And then if you continue in the same pattern 38 gets printed and 32 gets printed. For the right subtree... 90 77 62 88

Answer 1

A is a pre-order traversal, whereas B is an in-order traversal.

An easy way for you to figure out the order of printing is to look at how you visit the nodes themselves. I usually draw an outline around the outside of the tree (starting at the root and moving through the left or right based on the sub-tree you are traversing first). If I am doing a pre-order traversal, I print out a node whenever I move along its outside. If I am doing an in-order traversal, I print out a node only when I move under it (this makes sense when you look at in-order traversals, because you end up printing the leaves first; they are the first nodes you move under when you draw the outline). If I am doing a post-order traversal, I print out a node only when I move along its inside.

UPDATE

The reason 30 gets printed out after 5 and 8 is that you are not performing a purely pre-order traversal. You're jumping between a pre-order and an in-order traversal.

An easy way to figure out the order is to actually write down the steps your code goes through as you trace through it (I frequently use pen/pencil and paper to keep the information together). For example, you could do write out a call-stack like this:

A(60)
  printf(60)
  call B(60.left)
    B(30)
      call A(30.left)
        A(5)
          printf(5)
          call B(5.left)
            B(null)
          call B(5.right)
            B(8)
              call A(8.left)
                A(null)
              printf(8)
              call A(8.right)
                A(null)
      printf(30)
      call A(30.right)
        A(38)
        ...

You can easily see the order in which the nodes are printed, and more importantly, why you "jump" from printing 8 to printing 30 (one recursive call has ended and you're falling back one level).

Answer 2

Just write out the full execution stack over time. Like this:

A(60)
  printf
  B(30)
    A(5)
      ...
    printf
    A(38)
      ...
  B(90)
    ...

(The remainder of the tree left as an exercise to the reader.)

Then just go from top to bottom, writing down the results of the printf statements.

Answer 3

For starters, your code has a bunch of errors in it. I'm guessing it should be more like this:

struct treeNode{
  int data;
  struct treeNode *left, *right;
}

treeNode *tree_ptr;

void A(treeNode *node_ptr){
    if (node_ptr != NULL){  /// this could be just if(node_ptr)
        printf(“%d ,”,node_ptr->data);
        B(node_ptr->left);
        B(node_ptr->right);
    }   
}

void B(treeNode *node_ptr){
    if (node_ptr != NULL) {
        A(node_ptr->left);
        printf(“%d ,”,node_ptr->data);
        A(node_ptr->right);
    }
}   

You're also mixing two different traversal algorithms. A() is pre-order, B() is in-order. A() and B() should be calling themselves, not each other. (Yet another reason to use real variable/function names instead of A, B, and such.)

Answer 4

the trace as indicated above cannot be correct for either Pre-order or In-order Pre - 60 , 30, 5, 8 35 32 etc In - 5, 8, 30, 32, 35 etc.