Tree [Level Order Treversal]

This is a discussion on Tree [Level Order Treversal] within the C++ Programming forums, part of the General Programming Boards category; I have been looking on the net for Level Order Treversal Recursively some sites even said it is not possible ...

  1. #1
    Registered User cfrost's Avatar
    Join Date
    Apr 2004
    Posts
    119

    Smile Tree [Level Order Treversal]

    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
    Software is like sex it is good when it is free

  2. #2
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    thanks, but there's really no need for it. All of this is nicely covered in Prelude's tutorials.
    :wq

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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:
    Code:
    #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.
    My best code is written with the delete key.

  4. #4
    Registered User cfrost's Avatar
    Join Date
    Apr 2004
    Posts
    119
    Thank you all for immidiate response and sorry I forgot to search on CProgramming.com ....
    Software is like sex it is good when it is free

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 02:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 06:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21