JuniorCodeCommonNot answered yet
Count the left leaves of a binary tree
Count the left leaves of a binary tree. A node is a left leaf if it is its parent's left child and has no children of its own. A single-node tree (the root) has no left leaves.
Requirements:
- One DFS traversal; the "left" property must be known from the parent.
struct Node { Node* left; Node* right; int value; };
int countLeftLeaves(Node* root) {
// your code here
}Write the implementation.
The left-leaf property cannot be decided from a node alone — it depends on the parent. Recurse passing an isLeft flag: a node counts when it is a leaf (no children) and isLeft is true. Recurse into left with isLeft = true and into right with isLeft = false. The root is passed isLeft = false. O(n) time.
- ✗Counting all leaves regardless of whether they are left children
- ✗Trying to decide 'leftness' from the node itself instead of the parent context
- ✗Counting a single-node tree's root as a left leaf
- →Why can't a node decide on its own that it is a left leaf?
- →How would you instead sum the values of the left leaves?
Contents
Task
Count the left leaves of a tree (a left child with no children). In O(n).
Solution
struct Node { Node* left; Node* right; int value; };
static int dfs(Node* node, bool isLeft) {
if (!node) return 0;
if (!node->left && !node->right) // it is a leaf
return isLeft ? 1 : 0; // count only left ones
return dfs(node->left, true) // left child: isLeft = true
+ dfs(node->right, false); // right: isLeft = false
}
int countLeftLeaves(Node* root) {
return dfs(root, false); // root is not left
}Key points
- "Leftness" comes from the parent via the
isLeftflag, not derived from the node. - The root is passed
isLeft = false, so a lone root is not counted. - One DFS traversal, O(n) time.
Contents
