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 Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay