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
Author, Copyright and citation
Author
Author of the this article - Sylwester Wojnowski - is a sWWW web developer. He has been writing computer code for the websites and web applications since 1998.
Copyrights
©Copyright, 2024 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
Cite this article as:
Wojnowski, Sylwester. "Checking trees for sameness with recursion and spaceship operator in PHP." From sWWW - Code For The Web . https://swww.com.pl//main/index/checking-trees-for-sameness-with-recursion-and-spaceship-operator-in-php
Add Comment