Get Binary Tree Diameter between 2 longest nodes

getBinaryTreeDiameter.php

<?php

function hasLeftNode($node) {
	return array_key_exists(0, $node);
}

function hasRightNode($node) {
	return array_key_exists(1, $node);
}

function isLeftNodeArray($node) {
	return is_array($node[0]);	
}

function isRightNodeArray($node) {
	return is_array($node[1]);	
}

function getChildNodeArray($node) {
	return hasRightNode($node) && isRightNodeArray($node) ? $node[1] : $node[0];
}

function hasBothNodes($node) {
	return hasLeftNode($node) && hasRightNode($node);
}

function areBothNodesArray($node) {
	return hasBothNodes($node) && isLeftNodeArray($node) && isRightNodeArray($node);
}

function getHopsFromNode($node, $hop = 0) {
	$isNodeArray = is_array($node);
	// var_dump("====== getHopsFromNode starts here =======");
	// var_dump("hop: $hop isNodeArray: " . ($isNodeArray ? 'true' : 'false') . " node: " . var_export($node, true));
	if ($isNodeArray) {
		$hop += 1;
		// var_dump("hop: $hop areBothNodesArray: " . (areBothNodesArray($node) ? 'true' : 'false'));
		if (!areBothNodesArray($node)) {
			$childNodeArray = getChildNodeArray($node);
			// var_dump("childNodeArray: " . var_export($childNodeArray, true));
			return getHopsFromNode($childNodeArray, $hop);
		}
		$nestedNodeInfo = getBinaryTreeInfo([$node]);
		$longestTraverse = $nestedNodeInfo['longestTraverse'];
		$diameter = $nestedNodeInfo['diameter'];
		return ['diameter' => $diameter, "longestTraverse" => $longestTraverse];
	}
	// var_dump("hop: $hop");
	return $hop;
}

function getLongestTraverse($leftNodeHops, $rightNodeHops) {
	return $rightNodeHops > $leftNodeHops ? $rightNodeHops : $leftNodeHops;
}

function getBinaryTreeInfo($binaryTree)
{
	$leftNode = $binaryTree[0][0];
	$rightNode = $binaryTree[0][1];
	$rightNodeMaxHops = getHopsFromNode($rightNode);
	$leftNodeMaxHops = getHopsFromNode($leftNode);
	$hasNestedRightNodeBinaryTree = is_array($rightNodeMaxHops);
	$hasNestedLefNodeBinaryTree = is_array($leftNodeMaxHops);
	$nestedRightNodeBinaryTreeDiameter = $hasNestedRightNodeBinaryTree ? $rightNodeMaxHops['diameter'] : 0;
	$nestedLeftNodeBinaryTreeDiameter = $hasNestedLefNodeBinaryTree ? $leftNodeMaxHops['diameter'] : 0;
	$nestedRightNodeBinaryTreeLongestTraverse = $hasNestedRightNodeBinaryTree ? $rightNodeMaxHops['longestTraverse'] : 0;
	$nestedLeftNodeBinaryTreeLongestTraverse = $hasNestedLefNodeBinaryTree ? $leftNodeMaxHops['longestTraverse'] : 0;
	$nestedNodesDiameter = $hasNestedRightNodeBinaryTree && $hasNestedLefNodeBinaryTree ? $nestedLeftNodeBinaryTreeLongestTraverse + $nestedRightNodeBinaryTreeLongestTraverse + 2 + 1 : 0;
	var_dump("nestedNodesDiameter: $nestedNodesDiameter");
	var_dump("nestedRightNodeBinaryTreeDiameter: $nestedRightNodeBinaryTreeDiameter");
	var_dump("nestedLeftNodeBinaryTreeDiameter: $nestedLeftNodeBinaryTreeDiameter");
	var_dump("nestedRightNodeBinaryTreeLongestTraverse: $nestedRightNodeBinaryTreeLongestTraverse");
	var_dump("nestedLeftNodeBinaryTreeLongestTraverse: $nestedLeftNodeBinaryTreeLongestTraverse");
	if ($nestedNodesDiameter > $nestedLeftNodeBinaryTreeDiameter && $nestedNodesDiameter > $nestedRightNodeBinaryTreeDiameter) {
		return [
			'longestTraverse' => getLongestTraverse($nestedRightNodeBinaryTreeLongestTraverse, $nestedLeftNodeBinaryTreeLongestTraverse),
			'diameter' => $diameter,
		];
	} else if ($nestedLeftNodeBinaryTreeDiameter > $nestedNodesDiameter) {
		$rightNodeMaxHops = 0;
		$leftNodeMaxHops = $leftNodeMaxHops['diameter'] - 1;
	} else if ($nestedRightNodeBinaryTreeDiameter > $nestedNodesDiameter) {
		$leftNodeMaxHops = 0;
		$leftNodeMaxHops = $rightNodeMaxHops['diameter'] - 1;
	}
	$diameter = $leftNodeMaxHops + $rightNodeMaxHops;
	$diameter += 1; // 1 for counting the root node
	/*var_dump(
		"====== getBinaryTreeInfo starts here =======",
		"leftNodeMaxHops: $leftNodeMaxHops",
		"rightNodeMaxHops: $rightNodeMaxHops",
		"longestTraverse: $longestTraverse",
		"diameter: $diameter",
		"======= getBinaryTreeInfo ends here ======"
	);*/
	return [
		'longestTraverse' => getLongestTraverse($leftNodeMaxHops, $rightNodeMaxHops),
		'diameter' => $diameter,
	];
}

function getBinaryTreeDiameter($binaryTree)
{
	return getBinaryTreeInfo($binaryTree)['diameter'];
}

$sampleBinaryTree = [
	[
		[
			'level1LeftNodeChild',
			[
				'level2LeftNodeChild',
				[
					'level4RightNodeLeftChild',
					'level4LeftNodeRightChild'
				]
			]
		],
		[
			[
				[
					[
						[
							'level5RightNodeChild'
						]
					],
					'level3RightNodeChild',
				]
			],
		]
	]
];

// echo getBinaryTreeDiameter($sampleBinaryTree);
// Output: 9

$sampleBinaryTree2 = [
	[
		[
			[
				'level3LeftNodeChild',
				[
					[
						[
							'level4LeftNodeChild'
						]
					]
				]
			],
			[
				'level3LeftNodeChild',
				[
					[
						[
							'level4RightNodeChild'
						]
					]
				]
			]
		],
		[
			'level1RightNodeChild',
		]
	]
];

// echo getBinaryTreeDiameter($sampleBinaryTree2);
// Output: 9

$sampleBinaryTree3 = [
	[
		[
			[
				'level3LeftNodeChild',
				[
					[
						[
							'level4LeftNodeChild'
						]
					]
				]
			],
			[
				'level3LeftNodeChild',
				[
					[
						'level4RightNodeChild'
					]
				]
			]
		],
		[
			'level1RightNodeChild',
		]
	]
];

// echo getBinaryTreeInfoTreeDiameter($sampleBinaryTree3);
// Output: 8

$sampleBinaryTree4 = [
	[
		[
			[
				'level3LeftNodeChild',
				[
					[
						[
							'level4LeftNodeChild'
						]
					]
				]
			],
			[
				'level3LeftNodeChild',
				[
					[
						'level4RightNodeChild'
					]
				]
			]
		],
		[
			[
				[
					'level1RightNodeChild',
				]
			]
		]
	]
];

echo getBinaryTreeDiameter($sampleBinaryTree4);
// Output: 9