Good evening! Here's our prompt for today.

Finding the Sum of Right Leaves in a Binary Tree

Imagine a family tree, but instead of tracking your relatives, it's tracking numbers. Each "person" in this tree has at most two "children," and some have none. We call these childless nodes "leaves," and your task is to find the sum of leaves that are on the right side of their "parent."

Visualizing the Problem

In this illustration, the right leaves are 8 and 3. Their sum would be 11.

Preparing the Groundwork

Before diving into the solution, let's first establish what a Node in this tree looks like. We assume all nodes, even the root, follow this structure:

1class Node {
2	constructor(val) {
3		this.value = val;
4		this.left = null;
5		this.right = null;
6	}
7}

Constraints to Keep in Mind

• The tree has a maximum length of 100,000 nodes.
• All node values are integers, ranging from -2000 to 2000.
• The function should run in O(n) time complexity.
• The space complexity should be O(n) considering the call stack.

Function Signature

You need to implement the following function:

1function sumOfRightLeaves(root) {
2  return root;
3}

Understanding the Challenge

The function takes in the root node of the tree as an argument. Your goal is to traverse the tree and sum up all the right leaves.

So, how do we do that? Let's dive into the solution next.

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

def sumOfRightLeaves(root):

    return root

​

​

# class Node:

#   def __init__(self, val):

#     self.val = val

#     self.left = None

#     self.right = None

​

​

# Node definition

class Node:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

​

​

# Regular binary trees

tree1 = Node(4)

tree1.left = Node(1)

tree1.right = Node(3)

​

tree2 = Node(5)

tree2.left = Node(10)

tree2.left.left = Node(17)

tree2.left.right = Node(3)

tree2.right = Node(8)

Here's our guided, illustrated walk-through.

How do I use this guide?