Need some explanation about trees in C

Leaf *findLeaf(Leaf *R,int data)
{
  if(R->data >= data )
  {
    if(R->left == NULL) return R;
    else return findLeaf(R->left,data);
  }
  else
  {
     if(R->right == NULL) return R;
     else return findLeaf(R->right,data);
  }
}


void traverse(Leaf *R)
{
 if(R==root){printf("ROOT is %d\n",R->data);}
 if(R->left != NULL)
 {
    printf("Left data %d\n",R->left->data);
    traverse(R->left);
 }
 if(R->right != NULL)
 {
    printf("Right data %d\n",R->right->data);
    traverse(R->right);
 }
}

These code snippets works fine but i wonder how they works? I need a brief explanation about recursion.I am thankful for your helps.

Answers


A Leaf struct will look something like this:

typedef struct struct_t {
    int data;
    Leaf * left;   //These allow structs to be chained together where each node 
    Leaf * right;  //has two pointers to two more nodes, causing exponential
} Leaf;            //growth.

The function takes a pointer to a Leaf we call R and some data to search against, it returns a pointer to a Leaf

Leaf *findLeaf(Leaf *R,int data){

This piece of code decides whether we should go left or right, the tree is known to be ordered because the insert function follows this same rule for going left and right.

  if(R->data >= data ){

This is an edge case of the recursive nature of the function, if we have reached the last node in a tree, called the Leaf, return that Leaf.

An edge case of a recursive function has the task of ending the recursion and returning a result. Without this, the function would not finish.

    if(R->left == NULL) return R;

This is how we walk through the tree, Here, we are traversing down the left side because the data was larger. (Larger data is always inserted on at the left to stay ordered.) What is happening is that now we call findLeaf() with R->left, but imagine if we get to this point again in this next call.

It will become R->left->left in reference to the first call. If the data is smaller than the current node we are operating on we would go right instead.

    else return findLeaf(R->left,data);

Now we are at the case where the data was smaller than the current Node, so we are going right.

  } else {

This is exactly the same as with the left.

     if(R->right == NULL) return R;
     else return findLeaf(R->right,data);
  }
}

In the end, the return of the function can be conceptualized as something like R->right->right->left->NULL.

Lets take this tree and operate on it with findLeaf();

findLeaf(Leaf * root, 4) //In this example, root is already pointing to (8)

We start at the root, at the top of the tree, which contains 8.

First we check R->data >= data where we know R->data is (8) and data is (4). Since we know data is smaller than R->data(Current node), we enter the if statement.

Here we operate on the left Leaf, checking if it is NULL. It isn't and so we skip to the else.

Now we return findLeaf(R->left, data);, but to return it, we must solve it first. This causes us to enter a second iteration where we compare (3) to (4) and try again.

Going through the entire process again, we will compare (6) to (4) and then finally find our node when we comepare (4) to (4). Now we will backtrack through the function and return a chain like this:

R(8)->(3)->(6)->(4)

Edit: Also, coincidentally, I wrote a blog post about traversing a linked list to explain the nature of a Binary Search Tree here.


Need Your Help

How to stop startActivity from making two instances of the same Activity

android back-button

Activity A has a button and in its onclick it starts new activity B, the new activity only has minimal onCreate function.