SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem requires us to find the sum of all left leaves in a given binary tree. A left leaf is defined as a node that is a left child and does not have any children of its own. The solution should traverse the entire tree and accumulate the values of these left leaves.

Intuition

To identify left leaves, we need to traverse the binary tree and check each node to see if it is a left child and if it is a leaf node (i.e., has no children). By recursively traversing the tree, we can keep track of whether a node is a left child and, if it is a leaf, add its value to the total sum.

Approach

1. Start with a recursive depth-first search (DFS) function.
2. Traverse the tree by visiting the left and right children of each node.
3. Pass a boolean flag to the recursive function to indicate whether the current node is a left child or not.
4. When we reach a node that is a left child and also a leaf, add its value to the sum.
5. Recursively continue the traversal to ensure that all nodes are visited.
6. Return the accumulated sum at the end.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the tree. Each node is visited exactly once.

Space Complexity:

O(h), where h is the height of the tree. This is the space required by the recursion stack. In the worst case, the tree can be skewed, making the space complexity O(n).

Code

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) { return inorder(root, false); }

    int inorder(TreeNode* root, bool isLeft) {
        if (root == nullptr)
            return 0;

        if (isLeft && root->left == nullptr && root->right == nullptr)
            return root->val;

        return inorder(root->left, true) + inorder(root->right, false);
    }
};

Python

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        return self.inorder(root, False)

    def inorder(self, root: TreeNode, isLeft: bool) -> int:
        if not root:
            return 0
        
        if isLeft and not root.left and not root.right:
            return root.val

        return self.inorder(root.left, True) + self.inorder(root.right, False)

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return inorder(root, false);
    }

    private int inorder(TreeNode root, boolean isLeft) {
        if (root == null) return 0;

        if (isLeft && root.left == null && root.right == null) 
            return root.val;

        return inorder(root.left, true) + inorder(root.right, false);
    }
}

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function (root) {

    let sum = 0;
    inorder(root, 0);
    function inorder(root, check) {

        if (root == null) return;

        if (check && root.left == null && root.right == null) sum += root.val;

        inorder(root.left, 1);
        inorder(root.right, 0);
    };
    
    return sum;
};