Figuring BST algorithm

[peachslasher]

Hi all,

I am having trouble understanding BST recursive algorithm. Here is the code:

int maxDepth(struct node* node) {
  if (node==NULL) {
    return(0);
  }
  else {
    // compute the depth of each subtree
    int lDepth = maxDepth(node->left);
    int rDepth = maxDepth(node->right);

    // use the larger one
    if (lDepth > rDepth) return(lDepth+1);
    else return(rDepth+1);
  }
}

and this is the structure of my tree [int data, leftpointer, rightpointer]
Tree *a,*b, *leftsub, *rightsub, *d,*e, *f, *mytree;
e=new Tree(14,NULL,NULL);
d= new Tree(15,NULL, NULL);
leftsub= new Tree(18,e,d);
b= new Tree(22,NULL,NULL);
f= new Tree(80,NULL, NULL);
rightsub = new Tree(30, b,f);
mytree(20, leftsub, rightsub);
maxDepth(mytree);

here is what i understand:
1. mytree is called
2. because mytree is not null then int lDepth = maxDepth(node->left); is called, and at this moment ldepth= 0 and maxDepth(a)
3. the function goes back to the top, and again node a is not null therefore ldepth = 0 and maxdepth(e);

then i am not too sure whats happening after this.

It will be really great if you can help me explains how does this function works

Thanks heaps =D

[Alex Edwards]

From what it looks like, your ints ldepth and rdepth are declared then initialized to a value returned by a function.

Because the function must perform functionality/calculating, the variable doesn't receive a value until the function is complete.

The variable will never be "complete" until one of the nodes it encounters is null (basically, it will return zero when it hits a null node of a leaf node) then it will return whichever variable is greater before that node since the function returned zero.

Even if the two nodes at the "bottom" were identical (same depth) it wont matter, the right depth variable will be incremented one. Then the function will keep returning and incrementing rdepth by 1 until it reaches the node that first called the function (which should be the root) and then the function will finally return the depth of your tree.

Edit: Also keep in mind how the tree is being traversed. It checks the left nodes first then the right nodes, so eventually all of the nodes in the tree are scanned and it will keep going as "low" as possible to get the deepest node and then eventually start returning values based on whichever is deepest.

I redid your code some to emulate the tree. Forgive me if I'm supposed to make Tree derive from the node struct, I wasn't certain. Anywho...

#include <cstdlib>
#include <iostream>

using namespace std;

struct Tree{
       public:
              Tree *left;
              Tree *right;
              int item;
                     
              Tree(int value, Tree *leftNode, Tree *rightNode){item = value; left = leftNode; right = rightNode;};
};

int maxDepth(Tree* node){
  if (node==NULL){
    return(0);
  }
  else{
    // compute the depth of each subtree
    cout << "Checking the left of " << node->item << endl;
    int lDepth = maxDepth(node->left);
    cout << lDepth << ", " << node->item <<endl;
    cout << "Checking the right of " << node->item << endl;
    int rDepth = maxDepth(node->right);
    cout << rDepth << ", " << node->item <<endl;

    // use the larger one
    if (lDepth > rDepth) return(lDepth+1);
    else return(rDepth+1);
  }
} 

int main(int argc, char *argv[]){
   Tree *a,*b, *leftsub, *rightsub, *d,*e, *f, *mytree;
   e=new Tree(14,NULL,NULL);
   d= new Tree(15,NULL, NULL);
   leftsub= new Tree(18,e,d);
   b= new Tree(22,NULL,NULL);
   f= new Tree(80,NULL, NULL);
   rightsub = new Tree(30, b,f);
   mytree = new Tree(20, leftsub, rightsub);
   cout << maxDepth(mytree) << endl;
   
   delete mytree;
   delete rightsub;
   delete f;
   delete b;
   delete leftsub;
   delete d;
   delete e;
    
   cin.get();
   return EXIT_SUCCESS;
}

I made it give output AFTER maxDepth obtains the argument being analyzed, when maxDepth is called for the left of the argument and when maxDepth is called for the right.

If you draw out your tree (the way you organized it) you'll see how this program traverses it and then you may begin to understand why it accurately returns the depth of your tree.

[Alex Edwards]

Here is a better example, with more prints to show what is occurring in the tree--

#include <cstdlib>
#include <iostream>

using namespace std;

struct Tree{
       public:
              Tree *left;
              Tree *right;
              int item;
                     
              Tree(int value, Tree *leftNode, Tree *rightNode){item = value; left = leftNode; right = rightNode;};
};

int maxDepth(Tree* node){
  if (node==NULL){
  cout << "Reached a null node! Unwrapping!" << endl;
    return(0);
  }
  else{
    // compute the depth of each subtree
    cout << "Checking the left of " << node->item << endl;
    int lDepth = maxDepth(node->left);
    cout << lDepth << ", Recursing from maxDepth(node->left): " << node->item <<endl;
    cout << "Checking the right of " << node->item << endl;
    int rDepth = maxDepth(node->right);
    cout << rDepth << ", Recursing from maxDepth(node->right): " << node->item <<endl;

    // use the larger one
    if (lDepth > rDepth) return(lDepth+1);
    else return(rDepth+1);
  }
} 

int main(int argc, char *argv[]){
   Tree *a,*b, *leftsub, *rightsub, *d,*e, *f, *mytree;
   e=new Tree(14,NULL,NULL);
   d= new Tree(15,NULL, NULL);
   leftsub= new Tree(18,e,d);
   b= new Tree(22,NULL,NULL);
   f= new Tree(80,NULL, NULL);
   rightsub = new Tree(30, b,f);
   mytree = new Tree(20, leftsub, rightsub);
   cout << maxDepth(mytree) << endl;
   
   delete mytree;
   delete rightsub;
   delete f;
   delete b;
   delete leftsub;
   delete d;
   delete e;
    
   cin.get();
   return EXIT_SUCCESS;
}