Print all nodes of the same level from binary tree

This is a discussion on Print all nodes of the same level from binary tree within the C Programming forums, part of the General Programming Boards category; This is the scenario: 1. user inputs an int N for the desired level 2. if N is greater than ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    Print all nodes of the same level from binary tree

    This is the scenario:

    1. user inputs an int N for the desired level
    2. if N is greater than the total number of levels in the tree, repeat input
    3. if N is less than 0, repeat input
    4. if N is okay, print all the nodes belonging to this level.

    1-3 I know how to do, but 4 is a mystery

    I thought about putting all the nodes into an array, and then manually checking each of them if they are of the required level, but I'm not sure if that would take for ever

  2. #2
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    It depends how your binary tree is represented. Is this a struct containing two spanning nodes (left and right)? Or an array?

    Let's say your binary tree is an array:

    Code:
    nodes (i):  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
                | | | | | | | | | |  |  |  |  |  |
                | | | | | | | | | |  |  |  |  |  |
    levels:     0 1 1 2 2 2 2 3 3 3  3  3  3  3  3
    
             0
       1           2
     3    4     5     6
    7 8  9 10 11 12 13 14
    Index of left node of i-th node, is: i * 2 + 1
    Index of right node of i-th node, is: i * 2 + 2
    First node of n'th level is:
    2^n-1
    (number of nodes for each level is 2^n).
    Last edited by kmdv; 09-05-2010 at 10:23 AM.

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    It'd be like any other traversal function only you have to keep track of what level you're at. When you reach that level, print and stop going deeper.

    Totally untested mostly real C code :
    Code:
    void print_at_level(Node *node, int desired, int current)
    {
       if (node)
       {
          if (desired == current)
             print(node);
          else
          {
             print_at_level(node->right, desired, current + 1);
             print_at_level(node->left, desired, current + 1);
          }
       }
    }

    top level call would be something like :

    Code:
    print_at_level(root, 0, 5)
    Last edited by KCfromNC; 09-08-2010 at 07:19 AM. Reason: Told you it was untested

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    Quote Originally Posted by KCfromNC View Post
    It'd be like any other traversal function only you have to keep track of what level you're at. When you reach that level, print and stop going deeper.

    Totally untested mostly real C code :
    Code:
    void print_at_level(Node *node, int desired, int current)
    {
       if (node)
       {
          if (desired == current)
             print(node);
          else
          {
             print_at_level(node->right, desired, current + 1);
             print_at_level(node->left, desired, current + 1);
          }
       }
    }

    top level call would be something like :

    Code:
    print_at_level(root, 0, 5)
    One decremented parameter is enough.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How would you improve this binary tree delete function?
    By Nazgulled in forum C Programming
    Replies: 1
    Last Post: 02-20-2010, 05:38 PM
  2. Question about computing the number of nodes in a Binary Tree
    By Overworked_PhD in forum C Programming
    Replies: 3
    Last Post: 12-12-2009, 01:10 PM
  3. how to print a binary tree..
    By transgalactic2 in forum C Programming
    Replies: 6
    Last Post: 11-19-2008, 01:53 PM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. What kind of programs should I start writing?
    By Macabre in forum C++ Programming
    Replies: 23
    Last Post: 04-12-2003, 09:13 PM

Tags for this Thread


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