Re: binary tree question

From: Ben Pfaff (blp_at_cs.stanford.edu)
Date: 02/23/04 

Date: Mon, 23 Feb 2004 12:35:12 -0800

harko@cluj.astral.ro (Sebi) writes:

> given a binary tree is there any way to find the level that contains
> the highest number of nodes but without using an additional array for
> storing the number of nodes on each level. ?
>
> 1
> / \
> 2 3
> / \ / \
> 4 5 6 7
> /
> 8
>
> in the example above the third level is the level with the highest
> number of nodes.

Sure, if you don't care about runtime (following not tested or
even well-proofread):

/* Returns the number of nodes exactly LEVEL levels below NODE. */
int
count_nodes_in_level (struct node *node, int level)
{
  if (node == 0)
    return 0;
  else if (level == 0)
    return 1;
  else
    return (count_nodes_in_level (node->left, level - 1)
            + count_nodes_in_level (node->right, level - 1));
}

/* Returns the level in TREE with the most nodes. */
int
biggest_level (struct node *tree)
{
  int biggest_level = 0;
  int biggest_level_nodes = 0;
  int level;
  int level_nodes = -1;

  for (level = 0; level_nodes != 0; level++) {
    level_nodes = count_nodes_in_level (tree, level);
    if (level_nodes > biggest_level_nodes) {
      biggest_level = level;
      biggest_level_nodes = level_nodes;
    }
  }
  return biggest_level;
} 

-- 
Ben Pfaff 
email: blp@cs.stanford.edu
web: http://benpfaff.org

Relevant Pages

  • radix sort
    ... struct node *next; ... void freelist; ... int large_dig; ... kth digit of all no:s */ ...
    (comp.programming)
  • LinkedList Pointer (REPOST - diff version)
    ... struct node * next; ... No problem until you are dealing with a pointer variable. ... void Push(struct node** headRef, int newData); ... Given an int and a reference to the head pointer (i.e. a struct ...
    (comp.lang.c)
  • LinkedList Pointer (REPOST - diff version)
    ... struct node * next; ... No problem until you are dealing with a pointer variable. ... void Push(struct node** headRef, int newData); ... Given an int and a reference to the head pointer (i.e. a struct ...
    (comp.lang.c)
  • Re: radix sort
    ... struct node *next; ... you can only store objects of type int. ... why not just use an array instead of a linked ... digit (int num, int k) ...
    (comp.programming)
  • Re: free memory question
    ... pointer (ptr) dynamically allocated in function "test_free"? ... struct node* y; ... int main ... struct node* calc = NULL; ...
    (comp.lang.c)