DSA problem
Sum of Left Leaves
Given the root of a binary tree, return the sum of all left leaves — that is, leaf nodes that are themselves the left child of their parent. Right leaves and internal nodes are ignored.
A node qualifies for the sum iff it satisfies both conditions: it has no children (i.e. it is a leaf), and it is positioned as its parent's left child. Note that the root itself can never be counted: it has no parent and therefore cannot be a "left" leaf, even if both its children are null.
The most natural way to encode the position information is with an extra boolean parameter — is_left — passed down the recursion. When we recurse into a node's left child we pass True; when we recurse right we pass False. At each visit, if the current node is a leaf and is_left is True, we add its value to a running total.
This is a textbook preorder DFS: examine the current node first (apply the test), then recurse left and right. Time complexity is O(n) since every node is visited exactly once; space is O(h) for the recursion stack, where h is the height of the tree.
Examples
root = [3,9,20,null,null,15,7]24root = [1]0root = [1,2,3,4,5]4Constraints
- The number of nodes in the tree is in the range [1, 1000].
- -1000 <= Node.val <= 1000
- The tree is a valid binary tree.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.