This file assumes you already know what a binary tree is and that you already have a binary tree.
In case either of these two indispensable prerequisites is missing, you may consider reading my (not too long) file about Binary Trees.

Thus, I will also presume you know that each node of your binary tree can be either an instance of a previously defined class or, actually, also a mere array - arguably an associative array namely an array whose indexes are not numbers but literals.
Whether a binary tree should be arranged as an array or as a set of nodes which are instances of a class is essentially up to your choice. An array, being much simpler a data structure type, is a potential candidate to be considered a standard data type for binary trees; yet, no doubts that binary trees whose nodes are instances of a class make more powerful trees, for each node is endowed with all the possible methods available in the signature of the class template it instantiates, and by changing that template signature you would also instantaneously affect the behaviours of all the nodes of your binary tree.

If you don't have a data structure with a pattern, as a binary tree is, you may want to know that there are on this site a set of powerful scripts to traverse irregular matrixes in php and in javascript both.
As you may have noticed there is plenty of scripts and stuff here made freely available for you: pay an acknowledgement or keep the commented website url in the scripts if you're going to use them or to draw consistent ideas from them: that's my only reward.

A Marc Chagall painting

The scripts featured here are remarkably interesting for binary trees which are within the scope of a dictionary: that is, binary trees within the range of, say, 50,000 nodes up to 350,000 nodes.
They are arranged as a class whose name is:
binaryTreeSearch
Therefore to initialize it with a $foo placeholder name for a variable, all you have to do is:
$foo = new binaryTreeSearch();

I now assume you know that each node of a binary tree (search binary tree to be more precise) has at least a set of three parameters: a left and a right branch, plus a slot for the data, and that normally the left branch links another node whose value is inferior to the data held by its previous (sibling) node, and whereas the right branch holds a node whose data value is higher than the data value of its previous node.
Anyway this class is structured in a way that it is irrelevant whether the right node is bigger and the left smaller than their parent, as long as each node has two branches; and it is immaterial to this class whether the field names assigned as the left and right branches are exactly "left" and "right" as the tradition bequeaths or anything else: since you can pass arguments to every method of this class, within those arguments you can specify the specific and maybe different names that you have assigned to your nodes branched fields.

As a consequence of the above, this class has no explicitly stated constructor method.
Perhaps it would have been useful setting one, in order to assign only once the names of the right/left fields of your tree nodes as parameters passed to the constructor itself rather than passing them again each time you invoke a method. Yet I eventually decided to make these parameters passed each time to each single method, thus you can use one class instance of this binary tree search script to serve more than one binary tree whose node types could be instances of different classes with different, manifold field names, or maybe with nodes that are just arrays. It's just flexibility.

This class presumes that your binary tree so called leaves, namely those nodes that hold no further branches, have appended to their empty branches the keyword value null.

Also, this class methods discriminate throughout their codes between two options, namely whether a node is an instance of a class (check that by the built in PHP function named get_class) or whether it is an array (arguably associative).
Undoubtedly, this may seem querulous to you, and involves a price to pay as far as performances are concerned; yet when I craft my scripts I want them to account for as many options as possible, so that if you really don't need one, all you have to do is a savvy editing of the codes and remove it.
I provide you with a full range, for it is better to my eyes to accommodate all the possibility and remove one, rather than assume only one option and then see a script not to work because the incoming arguments didn't fit that limited assumption.

There are a few interesting things in this class.
When you say you want to traverse a binary tree, what you mean is that you want to implement some procedures so that you can gather all its nodes.
Now, it should be apparent that there could be different orders in which you can visit (traverse) the nodes, thus getting different types of reaped collections.
Potentially, you could arrange the nodes in as many combinatorial orders as they would allow, but obviously only a few of these orders are yielded after a regular pattern, and only those orders that reflect a pattern are of some logical interest.
The default methods normally employed when traversing a tree are the following ones:

1. preorder: this means that first you grab the data from the node, then you move on to its left and right branches. If N stands from Node data and L for Left branch and R for Right branch, the acronym is: NLR
2. inorder: this means that first you enter the left branch, then you grab the data from this node, then you enter its right branch: the acronym is: LNR.
3. postorder: this means that first you enter the left branch, then the right branch, then you grab the values of the node that held those branches: the acronym is: LRN.

Though all these methods may appear puzzling to you as far as their description may entail a plausible internal proceeding, they can work for they exploit the activation records, namely the stacks, that get built in by using recursion.
If you want to know what this all means, you can read my essay: Understanding Algorithms And Recursion.

Yet there are, as many books mention, also three logical complements to those just mentioned traversing methods, though they are rarely implemented:

1. NLR is complemented by NRL.
2. LNR is complemented by RNL.
3. LRN is complemented by RLN.

Not only my script takes care of producing all these possible traversals - a truly rare thing.
But moreover it achieves that by using one single method of the class (such method is named xOrder), which is so flexible that it accommodates all these possibilities without significantly degrading the performance as one might suspect.
Like in javascript we could use the associative power of every Object Oriented Language (as javascript is) to pass as a method parameters varying strings and yet make them fit a specific runtime, so we can do something similar with Php too, though Php is not a wholly Object Oriented language.

That is, in javascript something like:
var yourText="document";
window[yourText];
would address the document object. Yet if as yourText you would have passed say "location", you would have addressed the location bar object without having to change the internal settings of the statement
window[yourText]
but only changing the value held by yourText as an incoming argument. Namely the code does not change, only the incoming value held by an argument does.

To a great degree, it is possible to do something similar with Php too, and thus the method xOrder is capable of accommodating as many as those 6 different traversal methods without multiplying the code lines by that 6.
That is, if a standard minimal preorder method, in its recursive version, may take 6 lines of code, thus yielding 6*6=36, my xOrder method, and its private dependency named visit, would take 25 lines of code and these lines including the code for the optional discriminations on whether a node is a class instance or an array.

That's not all.
The class has also a method that can gather the nodes level by level (all the levels, or even setting that it must stop at a specific level). This is unusual for in most books I have read this obviously interesting (and pattern oriented indeed!) traversal is not contemplated.

Also, this class has a method that can reap (traverse) all the left branches and/or all the right branches.
Puzzling as it may seem, regardless this is exactly the most obviously interesting way to traverse a binary tree, all the books I have read so far, which are rather popular and -let's not be mistaken about this- incredibly good (for otherwise I would have not bothered spending $50 to buy each of them), completely fail not only to provide this type of traversals, but they don't even mention them apparently. And yet when arguing what type of traversal makes sense, given a structure like a binary tree the traversal of all its left or of all its right branches always seemed to me like precisely the prototype of a binary tree traversal and of the designed ideal pattern hinted at and sought for.

Here is your code. For the initialization of an instance as I said, with a placeholder variable name as $foo:
$foo = new binaryTreeSearch();

Here are the descriptions of your methods, their arguments, what they return, what they do.


With this method you can gather the nodes level by level, all the nodes which are ranked at one same level at once that is, till the end of the binary tree or till an optional max level depth is achieved.

The method stores the result (and returns it too) into a class variable named levels thus:
$foo->levels;
What is returned (and therefore stored in such levels class variables) is an array representing the levels, and whose each entry is an array itself: all the entries ranged in this latter array aren't but all the binary tree nodes pertaining to one level.
Beware that these latest entries are not copies of the nodes, but pointers to the actually passed binary tree, thus changing them would be immediately reflected in the binary tree too!

This method takes in the following arguments:

• $tree: your binary tree.
• $untilLevel: optional; it defaults to zero meaning scan all levels. If you pass it as a higher number, the method will limit to that amount of scans (root excluded) unless the level of the null values are reached.
• $leftField: a String. Defaults to "minor". Do pass it to flag what is the field name that your node class or node index (if array) uses for its field holding the link to the node whose value is lower than that of the current one.
• $rightField: a String. Defaults to "major". Do pass it to flag what is the field name that your node class or node index (if array) uses for its field holding the link to the node whose value is higher than that of the current one.

On a very banal tree whose nodes (imagined in a flushing line rather than in their structured binary tree shape) hold the values [1,4,15,16,20,25] namely as a tree

             16
          /      \
         4       25
         /\      /\
	1 15    20 
	/\ /\    /\
		 

a method call and its output, assuming the nodes are instances of a class named aNode, would look like and would produce:
$foo=new binaryTreeSearch();
$foo->allLevels($a_Binary_Tree);



This method traverses your binary tree gleaning all the left nodes in one array and all the right ones in an other one. Returns boolean true when finished.
The left nodes are stored in a class variable named lefts, thus:
$foo->lefts;
The right nodes are stored in a class variable named rights, thus:
$foo->rights;
These are arrays whose each entry is a node. That is the actual node of your binary tree, a pointer not a copy.

This method takes in the following arguments:

• $tree: your binary tree.
• $untilLevel: optional; it defaults to zero meaning scan all levels. If you pass it as another number, the method will limit to that amount of scans (root excluded).
• $leftField: a String. Defaults to "minor". Do pass it to flag what is the field name that your node class or node index (if array) uses for its field holding the link to the node whose value is lower than that of the current one.
• $rightField: a String. Defaults to "major". Do pass it to flag what is the field name that your node class or node index (if array) uses for its field holding the link to the node whose value is higher than that of the current one.

On a very banal tree whose nodes (imagined in a flushing line rather than in their structured binary tree shape) hold the values [1,4,15,16,20,25] namely as a tree

             16
          /      \
         4       25
         /\      /\
	1 15    20 
	/\ /\    /\
		 

a method call and its output, assuming the nodes are instances of a class named aNode, would look like and would produce:
$foo=new binaryTreeSearch();
$foo->leftRight($a_Binary_Tree);



This is the method that makes the standard and inverse preorder, inorder, and postorder traversals. It stores the gleaned entries in a class variable array named ordered, thus:
$foo->ordered;
This method returns an array and such array ranges all the gleaned nodes. These are not copies, but pointers to the actual binary tree nodes.

This method requires a bit of study. It takes in the following arguments:

• $tree: your binary tree.
• $visitOrder: Attention now!
  This must be an array.
  This array is of three entries and reflects the order in which you want to perform three actions: visit the node, enter the left branch, enter the right branch as previously described speaking of the acronyms such as:
  • array('visit', 'minor', 'major'); visit is a class keyword and can't be changed: you can modify the slot it is allocated in, but to signify that as first step you want to visit, then exactly the term "visit" must be passed as first.
    Conversely major and minor are string names that you can change if your node has its branches called after different conventions.
  • array('visit', 'major', 'minor'); visit is a class keyword and can't be changed: you can modify the slot it is allocated in, but to signify that as first step you want to visit, then exactly the term "visit" must be passed as first.
    Conversely major and minor are string names that you can change if your node has its branches called after different conventions.
  • array('minor', 'visit', 'major'); visit is a class keyword and can't be changed: you can modify the slot it is allocated in, but to signify that as second step you want to visit, then exactly the term "visit" must be passed as second.
    Conversely major and minor are string names that you can change if your node has its branches called after different conventions.
  • array('major', 'visit', 'minor'); visit is a class keyword and can't be changed: you can modify the slot it is allocated in, but to signify that as second step you want to visit, then exactly the term "visit" must be passed as second.
    Conversely major and minor are string names that you can change if your node has its branches called after different conventions.
  • array('major', 'minor', 'visit'); visit is a class keyword and can't be changed: you can modify the slot it is allocated in, but to signify that as third step you want to visit, then exactly the term "visit" must be passed as third.
    Conversely major and minor are string names that you can change if your node has its branches called after different conventions.
  • array('minor', 'major', 'visit'); visit is a class keyword and can't be changed: you can modify the slot it is allocated in, but to signify that as third step you want to visit, then exactly the term "visit" must be passed as third.
    Conversely major and minor are string names that you can change if your node has its branches called after different conventions.
• $collectOnlyData: defaults to zero. If passed as 1, rather than the full nodes, are collected only the value held by the node slot meant to hold the data rather than the right or left links too. If you pass this argument, you should arguably pass also the next one.
• $dataFieldName: defaults to 'data'. Is a String, pass it to flag what is the field name in your node instance where the actual node value is stored.

On a very banal tree whose nodes (imagined in a flushing line rather than in their structured binary tree shape) hold the values [1,4,15,16,20,25] namely as a tree

             16
          /      \
         4       25
         /\      /\
	1 15    20 
	/\ /\    /\
		 

a method call and its output, assuming the nodes are instances of a class named aNode, would look like and would produce:
$foo=new binaryTreeSearch();
$foo->xOrder($a_Binary_Tree, array('minor','visit','major')); /*typical inorder sequence*/



This method does not glean entries but merely searches for a given value passede as second argument.
If it finds no match in the binary tree, it returns boolean false, otherwise it returns a pointer (and not a copy) to the node whose data value corresponded to the searched one.
It stores the returned result also in a class variable named found, thus:
$foo->found;

It takes in the following arguments:

• $tree: your binary tree.
• $searchedValue: the value (String, Number?) you want to search for.
• $dataFieldName: a String, representing the field name that in your node is assigned to the field where the data is stored, or anyway the node field name where you want to check for the searched value argument. Defaults to 'data'.
• $leftFieldName: a String, representing the field name that in your node is assigned to the left branch. Defaults to 'minor'.
• $rightFieldName: a String, representing the field name that in your node is assigned to the right branch. Defaults to 'major'.