404. Sum of Left Leaves

[mah-shamim]

Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Example 1:

• Input: root = [3,9,20,null,null,15,7]
• Output: 24
• Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2:

• Input: root = [1]
• Output: 0

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -1000 <= Node.val <= 1000

[mah-shamim]

We can implement a solution using recursion. Given the constraints and requirements, we will define a function to sum the values of all left leaves in a binary tree.

1. Define the Binary Tree Node Structure: Since PHP 5.6 doesn’t support classes with properties as easily, we use arrays to represent the tree nodes.

2. Recursive Function: Implement a recursive function to traverse the tree and sum the values of left leaves.

Let's implement this solution in PHP: 404. Sum of Left Leaves

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    public function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

// Define a tree node as an associative array for simplicity
// ['val' => value, 'left' => left_child, 'right' => right_child]

// Function to compute the sum of left leaves
function sumOfLeftLeaves($root) {
    if ($root === null) {
        return 0;
    }
    
    $sum = 0;
    
    // Check if the left child is a leaf node
    if (isset($root['left'])) {
        if ($root['left']['left'] === null && $root['left']['right'] === null) {
            $sum += $root['left']['val'];
        } else {
            $sum += sumOfLeftLeaves($root['left']);
        }
    }
    
    // Recur for the right child
    $sum += sumOfLeftLeaves($root['right']);
    
    return $sum;
}

// Example usage:

// Create the binary tree [3,9,20,null,null,15,7]
$root = new TreeNode(3);
$root->left = new TreeNode(9);
$root->right = new TreeNode(20);
$root->right->left = new TreeNode(15);
$root->right->right = new TreeNode(7);

echo sumOfLeftLeaves($root); // Output: 24

// For a single node tree [1]
$root2 = new TreeNode(1);
echo sumOfLeftLeaves($root2); // Output: 0
?>

Explanation:

1. Tree Node Definition:

   • The createNode function creates a node with a value and optional left and right children.

2. Sum of Left Leaves Function:

   • The sumOfLeftLeaves function recursively traverses the tree.
   • It checks if the left child exists and if it's a leaf (i.e., it has no children). If so, it adds the value of this leaf to the sum.
   • It then recursively processes the right child to account for any left leaves that might be in the right subtree.

3. Example Usage:

   • For the given tree examples, the function calculates the sum of all left leaves correctly.

Complexity:

• Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited exactly once.
• Space Complexity: O(h), where h is the height of the tree, due to recursion stack space.

[basharul-siddike]

Thanks to solve the "Sum of Left Leaves" problem

[mah-shamim]

Thanks