Frontend School

Sum of Leaf Nodes in a Binary Tree

DSA
easy

Sum of Leaf Nodes in a Binary Tree

Easy
Tree
DFS
BFS
Binary Tree
Traversal

Overview

Trees are fundamental data structures widely used in computer science to represent hierarchical relationships. Understanding how to traverse and manipulate trees is crucial for solving many algorithmic problems, from file system navigation to parsing expressions. This problem focuses on identifying and aggregating specific nodes within a binary tree, laying a foundation for more complex tree-based data processing.

What you need to do / Task

Implement a function that calculates the sum of all leaf nodes in a given binary tree. A leaf node is defined as a node that has no children (i.e., both its left and right child pointers are null).

  1. Traverse the binary tree, starting from the root.
  2. Identify each node that qualifies as a leaf node.
  3. Sum the values of all identified leaf nodes.
  4. Return the total sum.

Input & output

Your function should have the following signature:

function sumLeafNodes(root: TreeNode | null): number
  • root: The root node of the binary tree. It will be null if the tree is empty.
  • Returns: An integer representing the sum of the values of all leaf nodes in the tree. If the tree is empty, the sum should be 0.

Clarifications

  • A node is considered a leaf if both node.left and node.right are null.
  • Node values (val) can be positive, negative, or zero.
  • If the input root is null, it signifies an empty tree.

Examples

1

Example 1

Input:

root = [3,9,20,null,null,15,7]

Output:

31

Note:

The leaf nodes are 9, 15, and 7. Their sum is 9 + 15 + 7 = 31.

2

Example 2

Input:

root = [1]

Output:

1

Note:

The root node itself is a leaf node as it has no children. Its value is 1.

3

Example 3

Input:

root = null

Output:

0

Note:

The tree is empty, so there are no leaf nodes. The sum is 0.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is between 0 and 10^4.
  • Node.val is an integer between -1000 and 1000.
  • The tree is a binary tree; no specific ordering (like BST) is guaranteed.

Out of scope

  • Validation of the input TreeNode structure (assume valid tree nodes).
  • Optimizations for extremely deep or skewed trees beyond standard recursive call stack limits (for 10^4 nodes, typical recursion depth is acceptable).

What interviewers evaluate

  • Correctness of the algorithm in identifying and summing leaf nodes.
  • Efficiency of the tree traversal, avoiding redundant operations.
  • Proper handling of edge cases, such as an empty tree or a tree with a single node.
  • Clarity, readability, and maintainability of the code.

Loading editor...