Left-Hanging Leaves
EasyTrees
Problem
A leaf is left-hanging when it is the left child of its parent. Given the root of a binary tree, return the sum of all left-hanging leaves (0 if there are none).
Example 1
- Input:
- root = [3, 9, 20, null, null, 15, 7]
- Output:
- 24
9 and 15 are leaves that are left children: 9 + 15 = 24.
Example 2
- Input:
- root = [1]
- Output:
- 0
The root is a leaf but it has no parent, so it is not left-hanging.
Constraints
- 0 ≤ number of nodes ≤ 5000
- -1000 ≤ node.val ≤ 1000
Hint
Show the first hint
A node cannot tell by itself whether it is a left child. Who knows that?
Walkthrough
How to approach it
01Clarify before coding
- Does the root count when alone? No, it has no parent.
- Does a left child with children count? No, it must be a leaf.
- Negative values? Yes, simply added.
02Brute force
Build a parent map, then for every leaf check whether it is its parent's left child.
Cost: O(n) time but O(n) extra memory for the parent map, which is unnecessary.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.