Sum of Left Leaves

Let’s solve this problem by using a depth-first search (DFS) approach, where we traverse the tree and whenever we find a left leaf node, we add its value to our sum. We define a helper function dfs to do this recursive traversal.

Here is the Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        def dfs(node, is_left):
            if not node:
                return 0
            if is_left and not node.left and not node.right:
                return node.val
            return dfs(node.left, True) + dfs(node.right, False)

        return dfs(root, False)

This solution works as follows:

  1. The dfs function traverses the tree. It takes two arguments: the current node, and a boolean is_left indicating whether the node is a left child.

  2. If the node is None, we return 0.

  3. If the node is a left leaf (i.e., is_left is True, and the node has no children), we return the node’s value.

  4. Otherwise, we recursively call dfs on the node’s left and right children. For the left child, we pass True for is_left; for the right child, we pass False.

  5. We call dfs on the root of the tree, passing False for is_left since the root is not a left child.

1
2
3
4
5
6
7
8
9

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        if root.left and not root.left.left and not root.left.right:
            return root.left.val + self.sumOfLeftLeaves(root.right)
        else:
            return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

Problem Classification

  1. Binary Tree: The problem deals with operations on a binary tree, which is a data structure with a node-based hierarchy.

  2. Tree Traversal: The task involves traversing through the binary tree, visiting each node to assess if it’s a left leaf.

  3. Summation: The problem requires summing up values of certain nodes in the binary tree.

  4. Leaves Identification: The problem involves identifying leaf nodes in the binary tree.

  5. Positioning: The problem involves determining the position of nodes in a binary tree, specifically identifying nodes that are left children of their parent nodes.

Language Agnostic Coding Drills

  1. Understanding Tree Structure: The first step is to comprehend the structure of a binary tree, with the root node, left child, and right child.

  2. Understanding Null or Empty Nodes: Learn how to check whether a node in a tree is null or empty.

  3. Understanding Leaf Nodes: Understand what a leaf node is, i.e., a node with no children.

  4. Tree Traversal: Understand how to traverse a tree. In this case, a depth-first search approach is being used, going from root to the left and right nodes recursively.

  5. Recursive Function: Understand how to write a recursive function that can traverse through the tree. Recursive functions call themselves with modified arguments until a base condition is met.

  6. Position Checking: Understand how to check if a node is the left child of another node. In this case, it checks whether root.left exists and whether root.left itself doesn’t have any children.

  7. Adding Values: Learn how to add values in a data structure, in this case, the values of the left leaf nodes.

The problem-solving approach for this problem would be:

  1. Start by checking if the root of the tree is null or not. If it is null, return 0.

  2. Next, check if the left child of the root exists and if it is a leaf node (it doesn’t have left or right children). If it is, add its value to the recursive call for the right child of the root.

  3. If the left child of the root is not a leaf node, call the function recursively for both the left and right children of the root, adding their results.

  4. The function eventually returns the sum of the values of all left leaves in the binary tree. The recursion ensures all nodes in the tree are visited, and the conditions within the function ensure that only left leaf nodes are considered in the sum.

Targeted Drills in Python

Please note that in real scenarios these drills would need a proper binary tree to function. For simplicity, we’ll represent tree nodes as lists, with the first element being the node value, the second element being the left child, and the third element being the right child.

  1. Understanding Tree Structure
1
2
3
4

root = [1, [2, None, None], [3, None, None]]
print("Root node value:", root[0])
print("Left child value:", root[1][0])
print("Right child value:", root[2][0])
  1. Understanding Null or Empty Nodes
1
2
3

node = [2, None, None]
if not node[1] and not node[2]:
    print("The node has no children.")
  1. Understanding Leaf Nodes
1
2
3
4
5
6
7
8

def is_leaf(node):
    return node[1] is None and node[2] is None

node1 = [1, None, None]  # leaf node
node2 = [2, [3, None, None], None]  # not a leaf node

print(is_leaf(node1))  # should print True
print(is_leaf(node2))  # should print False
  1. Tree Traversal
1
2
3
4
5
6
7
8

def traverse_tree(node):
    if node is not None:
        print(node[0])
        traverse_tree(node[1])
        traverse_tree(node[2])

root = [1, [2, [4, None, None], [5, None, None]], [3, None, None]]
traverse_tree(root)
  1. Recursive Function
1
2
3
4
5
6
7

def sum_values(node):
    if node is None:
        return 0
    return node[0] + sum_values(node[1]) + sum_values(node[2])

root = [1, [2, [4, None, None], [5, None, None]], [3, None, None]]
print(sum_values(root))  # should print 15
  1. Position Checking
1
2
3
4
5
6
7
8
9

def is_left_child(parent, child):
    return parent[1] == child

root = [1, [2, None, None], [3, None, None]]
child1 = root[1]
child2 = root[2]

print(is_left_child(root, child1))  # should print True
print(is_left_child(root, child2))  # should print False
  1. Adding Values
1
2
3
4
5
6
7
8
9

def sum_left_leaves(node):
    if node is None:
        return 0
    if node[1] and is_leaf(node[1]):
        return node[1][0] + sum_left_leaves(node[2])
    return sum_left_leaves(node[1]) + sum_left_leaves(node[2])

root = [1, [2, None, None], [3, [4, None, None], None]]
print(sum_left_leaves(root))  # should print 2 (only left leaf is 2)

All these drills contribute to understanding and solving the problem, and they build upon each other. The final solution integrates all these concepts.