Tree [Level Order Treversal]

[cfrost]

I have been looking on the net for Level Order Treversal Recursively some sites even said it is not possible so finally i got solution and posting here so u people can use

begin
if tree is null, return;

if level is 1, then
print(tree.root);
else if level greater than 1, then
levelorderAux(tree.left_subtree, level-1);
levelorderAux(tree.right_subtree, level-1);
endif
end

levelorder(tree)
begin
for d = 1 to height(tree)
levelorderAux(tree, d);
endfor
end

I will like this post to be archived by admin

[viaxd]

thanks, but there's really no need for it. All of this is nicely covered in Prelude's tutorials.

[Prelude]

>I have been looking on the net for Level Order Treversal Recursively
Good luck.

>some sites even said it is not possible
They're woefully misinformed. It's certainly possible, but it's also certainly impractical.

>so finally i got solution
If you simply found it then I'm sorry, but it's pretty worthless. If you developed the algorithm yourself then kudos for being interested and inventive enough to give it a shot.

Anyway, the algorithm is dreadfully inefficient. Consider how many recursive calls you would make over the course of traversing an entire tree. Even when the tree is small, it's obvious that you're doing far too much redundant work. I could hit you with theories and shtuff, but empirical evidence has always been my preference:

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  node *left, *right;

  node ( int init, node *lleft, node *lright )
    : data ( init ), left ( lleft ), right ( lright )
  {}
};

struct node *insert ( node *tree, int data )
{
  if ( tree == NULL )
    tree = new node ( data, 0, 0 );
  else if ( data < tree->data )
    tree->left = insert ( tree->left, data );
  else
    tree->right = insert ( tree->right, data );

  return tree;
}

int max ( int a, int b )
{
  return a > b ? a : b;
}

int height ( node *tree )
{
  if ( tree == 0 )
    return -1;

  return max ( height ( tree->left ), height ( tree->right ) ) + 1;
}

void level_order_aux ( node *tree, int level )
{
  if ( tree == 0 )
    return;

  if ( level == 0 )
    printf ( "%d ", tree->data );
  else if ( level > 0 ) {
    puts ( "Recurse left" );
    level_order_aux ( tree->left, level - 1 );
    puts ( "Recurse right" );
    level_order_aux ( tree->right, level - 1 );
  }
}

void level_order ( node *tree )
{
  for ( int d = 0; d <= height ( tree ); d++ )
    level_order_aux ( tree, d );
}

void pre_level_order ( node *header )
{
  node *save[50];
  int front = 0;
  int back = 0;

  if ( header == 0 )
    return;

  save[front++] = header;

  while ( front != back ) {
    header = save[back++];

    printf ( "%d ", header->data );

    if ( header->left != 0 ) {
      puts ( "Move left" );
      save[front++] = header->left;
    }

    if ( header->right != 0 ) {
      puts ( "Move right" );
      save[front++] = header->right;
    }
  }
}

int main()
{
  node *root = 0;

  for ( int i = 0; i < 15; i++ )
    root = insert ( root, rand() % 1000 );

  level_order ( root );
  puts ( "\n" );
  pre_level_order ( root );
  puts ( "" );
}

Compare and contrast the amount of work that is done by your solution as opposed to my solution. And keep in mind that this is a very small tree.

Yes, it's "possible" to simulate a queue with recursion, but it's also terribly wasteful and really only useful as a theoretical exercise. You wouldn't want to use such an algorithm in practice.

[cfrost]

Thank you all for immidiate response and sorry I forgot to search on CProgramming.com ....