Checking trees for sameness with recursion and spaceship operator in PHP

Created:16 Jul 2020 14:51:53 , in  Maths

At some point in your adventure with programming you are likely to find yourself in need of determining whether two trees are the same or not. This article describes two methods to do it. First on them relies on a recursive algorithm, the other, shorter, simpler and more versatile utilizes PHP's spaceship operator.

Recursion for determining sameness of two binary trees

Firstly let's look at how to find if two binary trees are the same using a recursive function. One such function is given below. It compares two trees node by node. Firstly it checks if both tree's roots exist, then if the data they carry is the same. If both are true the code proceeds to compare left and right children (and their children if any) in the same manner.

function sameBinaryTree($root1,$root2,$data = 'value',$left = 'leftChild',$right = 'rightChild'){
  // nothing to compare
  if($root1 === NULL && $root2 === NULL  ){
    return true;
  }

  // one of nodes to be compared does not exist 
  if($root1 === NULL || $root2 === NULL){
    return false;
  }

  // optional part
  // if data carried by both nodes being compared is not the same return false
  if($root1 -> {$data} !== $root2 -> {$data} ){
    return false;
  }
  // end of optional part 

  // if data carried by both parent nodes matches, proceed to examine child nodes
  if($root1 -> {$data} === $root2 -> {$data} && sameBinaryTree($root1 -> {$left},$root2 -> {$left})
    && sameBinaryTree($root1 -> {$right}, $root2 -> {$right})){
    return true;
  }
}

Determinig two trees sameness recursively

Let's prepare two simple 3-node trees to work on first:

class Node{
  public $leftChild = NULL;
  public $rightChild = NULL;
  public $value = NULL;
}

$nodeA = new Node;
$nodeA -> value = 'A';
 
$nodeB = new Node;
$nodeB -> value = 'B';
   
$nodeC = new Node;
$nodeC -> value = 'C';

$tree1 = $nodeA;
$tree1 = $nodeA -> leftChild = $nodeB;
$tree1 = $nodeA -> rightChild = $nodeC; 

$tree2 = $nodeA;
$tree2 = $nodeA -> leftChild = $nodeB;
$tree2 = $nodeA -> rightChild = $nodeC;

and check if they are the same. Here is one example of how to to do that:

sameBinaryTree($tree1,$tree2)
// => true

Determining sameness with the spaceship operator

Surprisingly, sameness of two trees can be determined using the spaceship operator (<=>):

Here is an example of that:

$tree1 <=> $tree2
// => 0

The spaceship operator returns 0 if two values are equal. On the other hand, if the outcome of a comparison is -1 or 1, values are not equal ( At this point we are not interested in determining which value is greater or smaller.).

Going beyond binary trees

As it turns out, the spaceship operator is clever enough to compare not just binary but also more complex trees. Here is an example of this:

// tree1 has 3 child nodes
$tree1 = $nodeA;
$tree1 = $nodeA -> leftChild = $nodeB;
$tree1 = $nodeA -> rightChild = $nodeC;
$tree1 = $nodeA -> borrowedChild = 22;

// tree2 is a binary tree
$tree2 = $nodeA;
$tree2 = $nodeA -> leftChild = $nodeB;
$tree2 = $nodeA -> rightChild = $nodeC;

$tree1 <=> $tree2
// => -1

so the two trees are not the same.

Conclusion

Determining if two trees are the same is not as easy as doing the same for strings or numbers. Trees are fairly complex data structures and working with them often relies on recursion, so likely on more complex code. Fortunately, with the arrival of the spaceship operator with PHP 7, there is a working and reliable alternative to at least one recursive algorithms which works on trees now.

Hopefully you have found this article interesting and useful. If you have something to add, you are welcome to leave a comment below.

This post was updated on 16 Jul 2020 15:33:33

Tags:  php ,  recursion ,  tree