Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Sum of Left Leaves solution and explanation

EasyBinary TreeBreadth-First SearchDepth-First SearchTree7 min read63.1% acceptanceUpdated 9 Apr 2026
Asked atGrammarlyMicrosoftAmazonMetaGoogleBloomberg
Practise Sum of Left Leaves
6:10
Sum of Left LeavesKevin Naughton Jr. · 6:10 · 25K viewsWatch on YouTube
9 more videos on this problem
  1. Sum of Left LeavesKevin Naughton Jr. · 6:10 · 25K views
  2. LeetCode Sum of Left Leaves Explained - JavaNick White · 7:20 · 12K views
  3. Sum of Left Leaves | 2 Approaches | META | Leetcode 404 | codestorywithMIKcodestorywithMIK · 19:49 · 6K views
  4. Amazon Coding Interview Question - Sum of Left Leaves (LeetCode)AlgosWithMichael · 16:17 · 5K views
  5. 404. Sum of Left Leaves | Binary Tree | Tree | DFSAryan Mittal · 7:00 · 3K views
  6. Leetcode - Sum of Left Leaves (Python)Timothy H Chang · 2:51 · 3K views
  7. Sum of Left Leaves - LeetCode 404 - PythonDeepti Talesra · 13:48 · 1K views
  8. Leetcode 404. Sum of Left Leaves (Python) Full ExplanationCooper Codes · 7:06 · 565 views
  9. Solving LeetCode 404. Sum of Left Leaves | Tree | Easy | Amazon | Google | DFSCode Harmony · 6:36 · 349 views
  10. Can You Find Sum of Leaves? (LeetCode 404: Sum of Left Leaves)Code With Zi · 5:09 · 281 views

The problem

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2:

Input: root = [1]
Output: 0

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -1000 <= Node.val <= 1000

Approach overview

Problem Overview: You are given the root of a binary tree and need to compute the sum of all left leaves. A left leaf is a node that is both a left child of its parent and has no children of its own. The task is essentially a traversal problem: visit each node and check whether its left child qualifies as a leaf.

Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))

This approach performs a standard recursive traversal of the binary tree. At each node, check whether the left child exists and whether that left child is a leaf (both left and right pointers are null). If so, add its value to the running sum. Otherwise, continue the recursion on both left and right subtrees. The key insight is that you don't need to process every leaf—only those reached through a left edge. Each node is visited once, giving O(n) time complexity where n is the number of nodes. The recursion stack grows up to the height of the tree, which results in O(h) auxiliary space.

This solution is concise and mirrors the natural structure of the tree. Most engineers prefer this version when solving problems involving recursive tree traversal because the logic stays close to the definition of the structure itself.

Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))

The iterative version replaces recursion with an explicit stack to simulate depth-first search. Push the root node onto a stack and repeatedly pop nodes for processing. For each node, check whether its left child exists and whether it is a leaf. If it is, add its value to the total. Otherwise push the left child to the stack so its subtree can be explored. The right child is also pushed when present so the traversal eventually covers the entire tree.

This method still visits every node exactly once, resulting in O(n) time complexity. The stack stores nodes along the current traversal path, so the space usage remains O(h), where h is the height of the tree. Iterative DFS is useful when recursion depth might be large or when you want more explicit control over traversal order in a tree structure.

Recommended for interviews: Recursive DFS is the solution most interviewers expect. It clearly demonstrates your understanding of tree traversal and keeps the implementation short and readable. Mentioning the iterative stack-based DFS shows deeper understanding and awareness of recursion limits. Both approaches achieve the optimal O(n) time complexity since every node must be inspected to determine whether it forms a left leaf.

Approach 1: Recursive Depth-First Search (DFS)

This approach involves using recursive DFS to traverse the tree. At each node, determine if it is a left leaf. If it is, add its value to the sum and recursively continue to search for more left leaves in the subtree.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def dfs(self, node, is_left):
        if not node:
            return 0
        if not node.left and not node.right and is_left:
            return node.val
        return self.dfs(node.left, True) + self.dfs(node.right, False)

    def sumOfLeftLeaves(self, root):
        return self.dfs(root, False)
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int dfs(TreeNode node, boolean isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null && isLeft) return node.val;
        return dfs(node.left, true) + dfs(node.right, false);
    }
    public int sumOfLeftLeaves(TreeNode root) {
        return dfs(root, false);
    }
}
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int dfs(TreeNode* node, bool isLeft) {
        if (!node) return 0;
        if (!node->left && !node->right && isLeft) return node->val;
        return dfs(node->left, true) + dfs(node->right, false);
    }
    int sumOfLeftLeaves(TreeNode* root) {
        return dfs(root, false);
    }
};
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var dfs = function(node, isLeft) {
    if (node === null) return 0;
    if (node.left === null && node.right === null && isLeft) return node.val;
    return dfs(node.left, true) + dfs(node.right, false);
};

var sumOfLeftLeaves = function(root) {
    return dfs(root, false);
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int dfs(struct TreeNode* node, int isLeft) {
    if (node == NULL) return 0;
    if (node->left == NULL && node->right == NULL && isLeft) return node->val;
    return dfs(node->left, 1) + dfs(node->right, 0);
}

int sumOfLeftLeaves(struct TreeNode* root) {
    return dfs(root, 0);
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public int Dfs(TreeNode node, bool isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null && isLeft) return node.val;
        return Dfs(node.left, true) + Dfs(node.right, false);
    }
    public int SumOfLeftLeaves(TreeNode root) {
        return Dfs(root, false);
    }
}

For Python, the recursive method involves a dfs helper that accumulates all the values of left leaves in a tree recursively. The use of a helper function makes it simple to track the 'left' node status.

Complexity

The approach is O(n) in time as each node is assessed once. The space complexity is O(h) due to the function stack during recursion, where h is the height of the tree.

Try this approach in the editor

Approach 2: Iterative Depth-First Search

This approach applies iterative DFS using a stack. By exploring each node iteratively, it checks if a node qualifies as a left leaf and accumulates its value to the sum. It manages to mimic a recursive pattern iteratively.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def sumOfLeftLeaves(self, root):
        if not root:
            return 0
        stack = [(root, False)]
        total_sum = 0
        while stack:
            node, is_left = stack.pop()
            if not node.left and not node.right and is_left:
                total_sum += node.val
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, True))
        return total_sum
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int sum = 0;
        Stack<TreeNode[]> stack = new Stack<>();
        stack.push(new TreeNode[]{root, null});
        while (!stack.isEmpty()) {
            TreeNode[] arr = stack.pop();
            TreeNode node = arr[0];
            TreeNode parent = arr[1];
            if (node.left == null && node.right == null && parent != null && parent.left == node) {
                sum += node.val;
            }
            if (node.right != null) {
                stack.push(new TreeNode[]{node.right, node});
            }
            if (node.left != null) {
                stack.push(new TreeNode[]{node.left, node});
            }
        }
        return sum;
    }
}
#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        int sum = 0;
        stack<pair<TreeNode*, bool>> stk;
        stk.push({root, false});
        while (!stk.empty()) {
            TreeNode* node = stk.top().first;
            bool isLeft = stk.top().second;
            stk.pop();
            if (!node->left && !node->right && isLeft) {
                sum += node->val;
            }
            if (node->right) {
                stk.push({node->right, false});
            }
            if (node->left) {
                stk.push({node->left, true});
            }
        }
        return sum;
    }
};
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var sumOfLeftLeaves = function(root) {
    if (!root) return 0;
    const stack = [{ node: root, isLeft: false }];
    let sum = 0;
    while (stack.length > 0) {
        const { node, isLeft } = stack.pop();
        if (!node.left && !node.right && isLeft) {
            sum += node.val;
        }
        if (node.right) {
            stack.push({ node: node.right, isLeft: false });
        }
        if (node.left) {
            stack.push({ node: node.left, isLeft: true });
        }
    }
    return sum;
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct Stack {
    struct TreeNode* node;
    int isLeft;
    struct Stack* next;
};

void push(struct Stack** stack, struct TreeNode* node, int isLeft) {
    struct Stack* new_node = (struct Stack*)malloc(sizeof(struct Stack));
    new_node->node = node;
    new_node->isLeft = isLeft;
    new_node->next = *stack;
    *stack = new_node;
}

void pop(struct Stack** stack) {
    if (*stack != NULL) {
        struct Stack* top = *stack;
        *stack = (*stack)->next;
        free(top);
    }
}

int sumOfLeftLeaves(struct TreeNode* root) {
    if (root == NULL) return 0;
    int sum = 0;
    struct Stack* stack = NULL;
    push(&stack, root, 0);
    while (stack != NULL) {
        struct TreeNode* node = stack->node;
        int isLeft = stack->isLeft;
        pop(&stack);
        if (node->left == NULL && node->right == NULL && isLeft) {
            sum += node->val;
        }
        if (node->right) {
            push(&stack, node->right, 0);
        }
        if (node->left) {
            push(&stack, node->left, 1);
        }
    }
    return sum;
}
using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public int SumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int sum = 0;
        Stack<(TreeNode node, bool isLeft)> stack = new Stack<(TreeNode, bool)>();
        stack.Push((root, false));
        while (stack.Count > 0) {
            var (node, isLeft) = stack.Pop();
            if (node.left == null && node.right == null && isLeft) {
                sum += node.val;
            }
            if (node.right != null) {
                stack.Push((node.right, false));
            }
            if (node.left != null) {
                stack.Push((node.left, true));
            }
        }
        return sum;
    }
}

The iterative approach leverages a stack to simulate recursion iteratively in Python. Nodes are pushed onto a stack with information on whether they are left children. Left leaf nodes values are accumulated forming the result.

Complexity

With time complexity at O(n) throughout all nodes browsing once, the stack utilization pertains to the space complexity marked as O(n).

Try this approach in the editor

Approach 3: Recursion

First, we check if root is null. If it is, we return 0.

Otherwise, we recursively call the sumOfLeftLeaves function to calculate the sum of all left leaves in root's right subtree, and assign the result to the answer variable ans. Then we check if root's left child exists. If it does, we check if it is a leaf node. If it is a leaf node, we add its value to the answer variable ans. Otherwise, we recursively call the sumOfLeftLeaves function to calculate the sum of all left leaves in root's left subtree, and add the result to the answer variable ans.

Finally, we return the answer.

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sumOfLeftLeaves(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    let ans = sumOfLeftLeaves(root.right);
    if (root.left) {
        if (root.left.left === root.left.right) {
            ans += root.left.val;
        } else {
            ans += sumOfLeftLeaves(root.left);
        }
    }
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
	if root == nil {
		return 0
	}
	ans := sumOfLeftLeaves(root.Right)
	if root.Left != nil {
		if root.Left.Left == root.Left.Right {
			ans += root.Left.Val
		} else {
			ans += sumOfLeftLeaves(root.Left)
		}
	}
	return ans
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, is_left: bool) -> i32 {
        if root.is_none() {
            return 0;
        }
        let node = root.as_ref().unwrap().borrow();
        let left = &node.left;
        let right = &node.right;
        if left.is_none() && right.is_none() {
            if is_left {
                return node.val;
            }
            return 0;
        }
        Self::dfs(left, true) + Self::dfs(right, false)
    }

    pub fn sum_of_left_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::dfs(&root, false)
    }
}
Try this approach in the editor

Approach 4: Stack

We can also convert the recursion in Solution 1 to iteration, using a stack to simulate the recursion process.

Similar to Solution 1, we first check if root is null. If it is, we return 0.

Otherwise, we initialize the answer variable ans to 0, and then initialize a stack stk and add root to the stack.

While the stack is not empty, we pop the top element root from the stack. If root's left child exists, we check if it is a leaf node. If it is a leaf node, we add its value to the answer variable ans. Otherwise, we add its left child to the stack. Then we check if root's right child exists. If it does, we add it to the stack.

Finally, we return the answer.

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sumOfLeftLeaves(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    let ans = 0;
    const stk: TreeNode[] = [root];
    while (stk.length) {
        const { left, right } = stk.pop()!;
        if (left) {
            if (left.left === left.right) {
                ans += left.val;
            } else {
                stk.push(left);
            }
        }
        if (right) {
            stk.push(right);
        }
    }
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) (ans int) {
	if root == nil {
		return 0
	}
	stk := []*TreeNode{root}
	for len(stk) > 0 {
		root = stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		if root.Left != nil {
			if root.Left.Left == root.Left.Right {
				ans += root.Left.Val
			} else {
				stk = append(stk, root.Left)
			}
		}
		if root.Right != nil {
			stk = append(stk, root.Right)
		}
	}
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Depth-First Search (DFS)

The approach is O(n) in time as each node is assessed once. The space complexity is O(h) due to the function stack during recursion, where h is the height of the tree.

Iterative Depth-First Search

With time complexity at O(n) throughout all nodes browsing once, the stack utilization pertains to the space complexity marked as O(n).

Recursion–
Stack–

Complexity analysis

ApproachTimeSpaceWhen to Use
Recursive Depth-First SearchO(n)O(h)Best general solution for binary tree traversal. Clean and easy to implement in interviews.
Iterative Depth-First Search (Stack)O(n)O(h)Useful when avoiding recursion depth limits or when explicit control of traversal stack is preferred.

Frequently asked questions

Is Sum of Left Leaves easy or hard?

Sum of Left Leaves is classified as an Easy problem on LeetCode with an acceptance rate above 60%. The challenge mainly involves correctly identifying a left leaf during tree traversal rather than implementing a complex algorithm.

Sum of Left Leaves Python/Java solution

Both Python and Java solutions typically implement DFS. In Python, recursion is commonly used with a helper function that checks whether a node's left child is a leaf. Java implementations follow the same logic using recursive methods or a stack-based traversal.

How to solve Sum of Left Leaves in O(n)?

Traverse the binary tree using DFS. At each node, check if the left child exists and whether that left child has no children. If both conditions hold, add its value to the total sum. Continue traversal through the remaining nodes so each node is processed once, resulting in O(n) time.

What is the best approach for Sum of Left Leaves?

Recursive Depth-First Search (DFS) is the most common and preferred approach. During traversal, check whether the current node's left child exists and is a leaf node. If it is, add its value to the sum; otherwise continue exploring both subtrees. This solution runs in O(n) time and O(h) space.

Is Sum of Left Leaves asked at Google/Amazon/Meta?

Tree traversal problems like Sum of Left Leaves frequently appear in technical interviews at companies such as Amazon, Google, and Meta. The problem tests your understanding of binary tree traversal, recursion, and identifying specific node conditions during traversal.

What data structure is used in Sum of Left Leaves?

The primary data structure is a binary tree. The algorithm typically uses depth-first search with either recursion (implicit call stack) or an explicit stack for iterative traversal.

What is the time complexity of Sum of Left Leaves?

The time complexity is O(n) because every node in the binary tree must be visited at least once to determine whether it forms a left leaf. Both recursive and iterative DFS solutions process each node exactly once.

Comments

Now write it yourselfClose this page and solve Sum of Left Leaves in the editor, without looking.
Practise Sum of Left Leaves