Sum of Left Leaves
Easy · Graphs · Explanation and code example
Sum Only Left Leaf Children
How it works
At each node, inspect its left child. Add its value only if that child has no children; otherwise recurse into it. Search the right subtree as well because it can contain left leaves farther down.
Steps
- Return zero for an empty root.
- Add a left child only when it is a leaf; otherwise recurse left.
- Always recurse into the right subtree.
Complexity
- Time: O(n).
- Space: O(h) recursion stack.
Things to watch for
- A root that is a leaf is not a left leaf.
- A left child with children does not count yet.
- Left leaves can occur inside right subtrees.
Python code example
class Solution:
def sumOfLeftLeaves(self, root: TreeNode | None) -> int:
if not root:
return 0
ans = 0
if root.left:
if not root.left.left and not root.left.right:
ans += root.left.val
else:
ans += self.sumOfLeftLeaves(root.left)
ans += self.sumOfLeftLeaves(root.right)
return ans
C++ code example
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr)
return 0;
int ans = 0;
if (root->left) {
if (root->left->left == nullptr && root->left->right == nullptr)
ans += root->left->val;
else
ans += sumOfLeftLeaves(root->left);
}
ans += sumOfLeftLeaves(root->right);
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.