methods of visiting the nodes on a level of a tree
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: methods of visiting the nodes on a level of a tree

  1. #1
    Join Date
    Jan 2010
    Posts
    3

    methods of visiting the nodes on a level of a tree

    Hello
    I know of only one method of visiting the elements on one level of a tree. This method is not very efficient. This is the way I do it(PHP implementation):
    Code:
    private function NextNode(&$node,$curlevel,$desiredlevel,&$nodesnr=null)
            {
                if($node == null)
                    return;
                $curlevel++;
    
                if($curlevel == $desiredlevel)
                {
                    $this->Visit($node);
                    if($nodesnr!==null)
                        $nodesnr++;
                }
    
                $this->NextNode($node->left,$curlevel,$desiredlevel,$nodesnr);
                $this->NextNode($node->right,$curlevel,$desiredlevel,$nodesnr);
            }
    I travese all the nodes of the tree in depth(inorder) and I check if teh level is equal to my desired level and if so I visit that node. I also keep track on the number of nodes but that is not relevant to the question.
    This is inefficient because it goes throgh the entire tree.

    Does anyone know of a better(more efficient) sollution?
    Thank you in advance

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: methods of visiting the nodes on a level of a tree

    Quote Originally Posted by para15000 View Post
    Does anyone know of a better(more efficient) sollution?
    One way is to stop going deeper when you've reached the desired level. You just put in a return at the end of the if-statement where you check that the current level equals the desired level.

    Another way is to traverse the tree once and build a linked list of tree nodes for each level. You can keep the linked lists in an array at the index corresponding to the level. When you want a certain level it's just to pick the linked list for that level in the array.

  3. #3
    Join Date
    Jan 2010
    Posts
    3

    Re: methods of visiting the nodes on a level of a tree

    Quote Originally Posted by nuzzle View Post
    One way is to stop going deeper when you've reached the desired level. You just put in a return at the end of the if-statement where you check that the current level equals the desired level.
    I don't see what you mean. If put a return at the end of the if statement after I chekc the level then only the first of the nodes on that level will be returned. I want to return all of them. Maby I don't understand exactly what you mean ...

    Quote Originally Posted by nuzzle View Post
    Another way is to traverse the tree once and build a linked list of tree nodes for each level. You can keep the linked lists in an array at the index corresponding to the level. When you want a certain level it's just to pick the linked list for that level in the array.
    This I did but not with a linked list I am using a object-oriented approach so I just stored the level of a node inside the each node object when I build the tree. So I already thought of this ... sorry I forgot to say. Or is this not related to what you meant

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: methods of visiting the nodes on a level of a tree

    Quote Originally Posted by para15000 View Post
    I don't see what you mean. If put a return at the end of the if statement after I chekc the level then only the first of the nodes on that level will be returned. I want to return all of them. Maby I don't understand exactly what you mean ...
    It should look like this,
    Code:
                if($curlevel == $desiredlevel)
                {
                    $this->Visit($node);
                    if($nodesnr!==null)
                        $nodesnr++;
                    return;
                }
    This will stop the recursion from going deeper than desiredlevel but the recursion will continue throughout the tree so that all nodes at the desiredlevel depth will be visited.

    This I did but not with a linked list I am using a object-oriented approach so I just stored the level of a node inside the each node object when I build the tree. So I already thought of this ... sorry I forgot to say. Or is this not related to what you meant
    Storing the level inside each node is not what I'm talking about. I'm talking about keeping all nodes belonging to a certain level in a separate data structure outside the tree. It could be a linked list or an array or whatever. I has nothing to do with whether you're using OO or not.

    You get two data structures. The tree itself and a list of nodes for each tree level. You pick the list for a certain level and when you scan it you get all nodes belonging to this level.
    Last edited by nuzzle; January 24th, 2010 at 01:06 PM.

  5. #5
    Join Date
    Jan 2010
    Posts
    3

    Re: methods of visiting the nodes on a level of a tree

    Quote Originally Posted by nuzzle View Post
    Code:
                if($curlevel == $desiredlevel)
                {
                    $this->Visit($node);
                    if($nodesnr!==null)
                        $nodesnr++;
                    return;
                }
    Yes you are right this is a good improvement. It doesn't prevent all the nodes from being visited. THank you.

    Quote Originally Posted by nuzzle View Post
    Storing the level inside each node is not what I'm talking about. I'm talking about keeping all nodes belonging to a certain level in a separate data structure outside the tree. It could be a linked list or an array or whatever. I has nothing to do with whether you're using OO or not.

    You get two data structures. The tree itself and a list of nodes for each tree level. You pick the list for a certain level and when you scan it you get all nodes belonging to this level.
    I see.And this would also be done when the tree is constructed? Right?

  6. #6
    Join Date
    May 2009
    Posts
    2,413

    Re: methods of visiting the nodes on a level of a tree

    Quote Originally Posted by para15000 View Post
    Yes you are right this is a good improvement. It doesn't prevent all the nodes from being visited.
    No it doesn't, but you don't have to visit any nodes below desiredlevel and that can be a substantial saving considering that the bulk of the nodes tend to be at the deepest levels.

    I see.And this would also be done when the tree is constructed? Right?
    That's a possibility but in principle it can be done at any time. And of course if the tree is changed structurally the "level lists" must be updated to reflect that.

    This solution is the fastest because you visit only exactly the nodes at desiredlevel. The drawback is that it requires an additional data structure which needs to be updated each time the tree changes. To what extent this is a problem depends on how often the tree is changed of course. If it never changes the only cost is the extra data structure.
    Last edited by nuzzle; January 25th, 2010 at 12:11 AM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center