BTR Depth

[ogito]

I need to write a routine that computes the maximum depth of the tree and run it after each insert and print out the depth. I've tried writing the code but it doesn't print out the depth! Can anyone help??

node *insert(int value, node *n) 
{
  if (n == NULL) 
  {
    return mkleaf(value) ; 
  } 
  if (value <= n -> contents )
  {
    n -> left = insert(value, n -> left) ; 
  }
  else 
  {
    n -> right = insert(value, n -> right) ; 
  }
  return n ; 
} 

int printnode(node *n)
{
  printf(&quot;node at %p value=%d left=%p right=%p\n&quot;, n, n -> contents, n -> left, n -> right) ; 
} 

node *mknode(int value, node *left, node *right)
{
   node *res = (node *)malloc(sizeof (node)) ; 
   res -> contents = value ; 
   res -> left = left ; 
   res -> right = right ; 
   return res ; 
} 

node *mkleaf(int value) 
{
  return mknode (value, NULL, NULL) ; 
} 

int preorder(node *n)
{
  if (n == NULL) return ; 
  preorder (n -> left) ; 
  printf (&quot;%d &quot;, n -> contents) ; 
  preorder (n -> right) ; 
}

 

[Salem]

I don't see any code for calculating the depth...


--

http://www.catb.org/~esr/faqs/smart-questions.html

 

[lionelhill]

nor do I. But if you have just inserted a (single) node into the tree, the most extra depth you can have added to the tree is 1. Therefore rather than searching the entire tree to find the deepest branch after inserting a node, the better approach is to detect whether you had to go to the greatest current depth of the tree to insert your node, and if so, add one to the greatest current depth. This avoids traversing the entire tree (and if you're going to traverse the entire tree, you might as well forget binary trees anyway. Their whole point is as a data structure that allows you to arrive somewhere without all that trouble! By the way, this problem crops up here very regularly. I wonder if it's in someone's course.)

 

[ogito]

This is what I have so far for depth

int depth( node * n )
{
  int r, l; /* right and left count */

  /* early-out if empty */
    if( n==0 )
    {
      /* tree is empty */
      return 0;
    }

  /* initialize to zero */
    r=l=0;

  /* count max in both directions */
    if( n->right )
    r=depth(n->right);

    if( n->left )
    l=depth(n->right);

  /* get higher count; store in r */
    if( l > r )
    r=l;

  /* return the depth of largest child + this node */
    return r+1;
}

 

[Salem]

if( n->right )
r=depth(n->right);

if( n->left )
l=depth(n->right);


Typo!
you do n->right both times


--

http://www.catb.org/~esr/faqs/smart-questions.html

 

[lionelhill]

... but remember this small piece of code hides a very large amount of tree-searching!