# Traversing trees in pre-order recursively in PHP

Created:03 Jul 2017 13:58:12 , in  Maths,  Web development

Like in the real world, trees are ubiquitous in computer programming today. Frequently tree data structure turns out to be a perfect choice for modelling a naturally occurring phenomena and not only them these days. The bad news is, unlike one-dimensional arrays or other data structures which can be traversed in linear order, or simply speaking - pretty painlessly, excluding the simplest cases, trees cannot.

However, there is also a good news. For many years trees are well-researched and better and better understood. There exists abundance of information on them both online and in Maths literature. Moreover, over recent decades there have been devised some very clever schemes for traversing trees efficiently.

It is worth nothing, that at least in the field of computer programming, I'm not sure about climbing trees in the real world, recursion is frequently a tool to employ for handling trees.

Recursion can be difficult to follow at times. On the other hand, especially if written carefully, it reduces amount of code needed to perform a complex task. Moreover, or perhaps first of all, it is a perfect technique for dealing with recursively defined data structures - trees are such structures.

## Depth-first pre-order tree traversal

Among others, a tree can be traversed in pre-order, which is a sort of depth-first tree traversal method. In this method, which start from visiting the "top-most" node, the goal is to reach the lowest laying nodes (leafs) from left to right (or otherwise) first. While traversing towards the bottom, if present, intermediate nodes (branches), are visited. Once all terminal nodes (leafs) for given branch have been visited, traversing moves on to its siblings and stops when all leafs in the tree have been reached.

Suppose, there is a tree like this:

``````
a
/ \
b   c
/ \   \
d   e   f
``````

Traversing it in pre-order from left to right will result in visiting all the nodes in the following order: a , b , d , e , c , f .

## SWWWTreeTraversal class

SWWWTreeTraversal is a PHP class for traversing trees depth-first I wrote some time ago. It uses recursion and pre-order method of traversing this data structure. It can traverse trees whose nodes are numbers, strings, associative arrays or objects (when extended) among others. It can also be extended freely.

Here is the code:

``````
/*
Class: SWWWTreeTraversal
Description: Recursive tree traversal in pre-order
Author: Sylwester Wojnowski
WWW: wojnowski.net.pl

Configuration parameters:
\$tree - a tree to be traversed

Methods:
get - get output from traversing a tree
return value: array
*/
class SWWWTreeTraversal{
protected \$tree;
protected \$output = array();

public function __construct(\$conf){
\$this -> tree = isset(\$conf['tree']) ? \$conf['tree'] : array();
\$this -> preorder(\$this -> tree);
}

protected function preorder(\$nodes){

if(empty(\$nodes)){
return;
}

foreach(\$nodes as \$node){
\$this -> visit_root(\$node);

\$this -> visit_children(\$node);
}
}

protected function visit_root(\$root){
if(! is_array(\$root) && !is_object(\$root)){
\$this -> output[] = \$root;
}
}

protected function visit_children(\$children){
if(is_array(\$children)){
\$this -> preorder(\$children);
}
}

public function get(){
return \$this -> output;
}
}
``````

## Configuration and use

SWWWTreeTraversal accepts associative array of configuration options, with exactly one item in it - a tree to be traversed.

## Examples of traversing trees with SWWWTreeTraversal

Once configured and instantiated SWWWTreeTraversal outputs array of values which can be obtained using "get" method.

``````
a
/ \
b   c
/ \   \
d   e   f
``````

And here is a piece of code needed to traverse the tree

``````
# the tree in the form digestible to PHP:
\$tree = array(
'a',
array(
'b',
array('d','e')
),
array(
'c',
array('f')
)
);

# configuration options:
\$conf = array(
'tree' => \$tree
);

# instantiate SWWWTreeTraversal
\$instance = new SWWWTreeTraversal(\$conf);
# get output:
\$instance -> get()
=> array('a','b','d','e','c','f')

``````

The same can be done for tree made of numbers:

``````
1
/ \
2   5
/ \   \
3   4   6
``````

Here is PHP code:

``````
\$tree = array( 1, array(2,array(3,4)), array(5,array(6)) );
\$conf = array('tree' => \$tree);

\$instance = new SWWWTreeTraversal(\$conf);
\$instance -> get()
=> array(1,2,3,4,5,6)
``````

Trees made up of associative arrays can be traversed:

``````
a
|_ _
| | |
b e c
| |
d f
``````

Here is PHP code for the case:

``````
\$tree = array(
'name' => 'a',
'children' => array(
array(
'name' => 'b',
'children' =>  array(
'name' => 'd',
'children' => array()
)
),
array(
'name' => 'e',
'children' =>  array(
'name' => 'f',
'children' => array()
)
),
array(
'name' => 'c',
'children' =>  array()
)
)
);

\$conf = array('tree' => \$tree);
\$instance = new SWWWTreeTraversal(\$conf);
\$this -> assertEquals(array('a','b','d','e','f','c'),\$instance -> get());
``````

## Extending SWWWTreeTraversal

Nothing stops you from extending SWWWTreeTraversal:

SWWWTreeTraversalObj, which is an extension to SWWWTreeTraversal, handles traversing trees of objects:

``````
class SWWWTreeTraversalObj extends SWWWTreeTraversal{
protected \$p_children;

public function __construct(\$conf){
\$this -> p_children = isset(\$conf['p_children']) ? \$conf['p_children'] : 'children';
parent::__construct(\$conf);
}

protected function visit_root(\$root){
\$this -> output[] = \$root;
}

protected function visit_children(\$children){
if(is_object(\$children)){
\$this -> preorder(\$children);
}
}
}
``````

Here is a small tree to be traverse with it:

``````
o
/
o
/ \
o   o
/     \
o       o
``````

And here is traversal PHP code:

``````
\$tree = (object)array(
'children' => (object)array(
'children' => (object)array(
(object)array(
'children' => (object)array(),
(object)array(
'children' => (object)array()
)
)
)
)
);

\$conf = array('tree' => \$tree);

\$instance = new SWWWTreeTraversalObj(\$conf);
count(\$instance -> get());
=> 6
``````

Finally, 'get' also can be overwritten to do something more useful than just returning node values. Your imagination is the limit here.

## Final thoughts

SWWWTreeTraversal is a basic and readily extensible PHP class which makes traversing trees easy. In this article I have focused on basic use examples for it. In the follow-up I'm going to do something useful using the class.

This post was updated on 03 Jul 2017 14:00:30

Tags:  data structure ,  php ,  recursion

### Author

Author of the above article, Sylwester Wojnowski, enjoys sWWW writing computer code in PHP, JavaScript and BASH, and some other things he wrote more on on the About page of this website.

©Copyright, 2021 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

### Citation

Wojnowski, Sylwester. "Traversing trees in pre-order recursively in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/traversing-trees-in-pre-order-recursively-in-php

## You might also like

• ### Switching from Mcrypt to OpenSSL engine in Kohana application

WEB DEVELOPMENT

• ### Developing for browser with mocha, chai and window node modules

WEB DEVELOPMENT

• ### Turning OOP class to graph for better code composition and understanding

WEB DEVELOPMENT

• ### Geocoding with HERE APIs and Vue.js

WEB DEVELOPMENT

• ### JSON object in asynchronous HTTP request

WEB DEVELOPMENT

Allowed BB Code - style tags: [b][/b], [i][/i], [code=text][/code],[code=javascript][/code],[code=php][/code],[code=bash][/code],[code=css][/code],[code=html][/code]

I constent to processing my data given through this form for purposes of a reply by the administrator of this website.