Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

methods of visiting all the elements on a given level of a binary tree

parapara Member Posts: 2
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);
}
[/code]
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

Comments

  • alienkineticsalienkinetics Member Posts: 5
    I would make the variables $curlevel, $desiredlevel and $nodesnr class variables to reduce stack usage, as stack movements is a major slowdown.

    Also, there is no need to traverse behond your desired level, so when you reach that level stop traversing. This requires you to increase the curlevel when you enter the function, and decrease when you exit.

    But, the fact is. If you want all the leaf nodes of a tree, then you need to traverse the entire tree. The only way arround this would be a second order list of leaf nodes.

    Im also unsure why you send *node by reference. It means a function could stuff up your tree structure if it changes $node, which is bad.

    [code]
    private function NextNod($node)
    {
    if($node) {
    $this->curlevel++;
    if($this->curlevel == $this->desiredlevel) {
    $this->Visit($node);
    if($this->nodesnr !== null) $this->nodesnr++;
    } else
    {
    $this->NextNode($node->left);
    $this->NextNode($node->right);
    }
    $this->curlevel--;
    }
    }
    [/code]
Sign In or Register to comment.