DEV Community

Cover image for 404. Sum of Left Leaves
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

404. Sum of Left Leaves

404. Sum of Left Leaves

Difficulty: Easy

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:

leftsum-tree

  • 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

Solution:

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) {
        ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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
?>
Enter fullscreen mode Exit fullscreen mode

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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay