Categories

# Binary tree – average sum Level – php – facebook

``````
class Node {

public \$value;
public \$left;
public \$right;

public function __construct(int \$value)
{
\$this->value = \$value;
\$this->left = null;
\$this->right = null;
}
}

class Solution {

public function bfs(\$node, &\$hashmap, \$level)
{

if(\$node === null) {
return;
}

\$queue = new SplQueue();

if(\$node->left)
{
\$queue->enqueue(\$node->left);
}

if(\$node->right)
{
\$queue->enqueue(\$node->right);
}

while (\$queue->count() > 0) {

\$childNode = \$queue->pop();

\$hashmap[\$level][] = \$childNode->value;

\$this->bfs(\$childNode, \$hashmap, \$level + 1);

}

}

public function AverageSumLevel(\$node)
{
\$hashmap = [];
\$level = 0;
\$hashmap[\$level][] = \$node->value;
\$this->bfs(\$node, \$hashmap, \$level + 1) ;

foreach (\$hashmap as \$level => \$values)
{
\$result[] = array_sum(\$values) / count(\$values);
}

return \$result;
}
}

\$node5 = new Node(5);
\$node5->left = new Node(4);
\$node5->right = new Node(8);

\$node5->left->left = new Node(2);
\$node5->left->right = new Node(1);

\$node5->right->right = new Node(9);
\$node5->right->right->right = new Node(12);

\$solution = new Solution();
\$res = \$solution->AverageSumLevel(\$node5);
var_dump(\$res);``````