Sum Of Left Leaves

                                            
/**
 * Definition for a binary tree node.
 * 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;
        if (root->left && !root->left->left && !root->left->right) {
            sum += root->left->val;
        }
        sum += sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
        return sum;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int sum = 0;
        
        if (root.left != null && root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        }
        
        sum += sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        
        return sum;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int sumOfLeftLeaves(struct TreeNode* root){
    if(root == NULL)
        return 0;
    
    int sum = 0;
    
    if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
        sum += root->left->val;
    
    sum += sumOfLeftLeaves(root->left);
    sum += sumOfLeftLeaves(root->right);
    
    return sum;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int SumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int sum = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        }
        
        sum += SumOfLeftLeaves(root.left);
        sum += SumOfLeftLeaves(root.right);
        
        return sum;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val);
 *     this.left = (left===undefined ? null : left);
 *     this.right = (right===undefined ? null : right);
 */
var sumOfLeftLeaves = function(root) {
    let sum = 0;
    
    const dfs = (node, isLeft) => {
        if (!node) return;
        
        if (!node.left && !node.right && isLeft) {
            sum += node.val;
            return;
        }
        
        dfs(node.left, true);
        dfs(node.right, false);
    }
    
    dfs(root, false);
    
    return sum;
};

                                            
/**
 * 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 {
    let sum = 0;
    
    const dfs = (node: TreeNode | null, isLeft: boolean) => {
        if (!node) return;
        
        if (!node.left && !node.right && isLeft) {
            sum += node.val;
        }
        
        dfs(node.left, true);
        dfs(node.right, false);
    };
    
    dfs(root, false);
    
    return sum;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     var val: Int
 *     var left: TreeNode?
 *     var right: TreeNode?
 *     init() { self.val = 0; self.left = nil; self.right = nil; }
 *     init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 */

class Solution {
    func sumOfLeftLeaves(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        
        var sum = 0
        
        if let left = root.left, left.left == nil, left.right == nil {
            sum += left.val
        }
        
        sum += sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right)
        
        return sum
    }
}

                                            
/**
 * 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
    }
    
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
        return root.Left.Val + sumOfLeftLeaves(root.Right)
    }
    
    return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left, @right = left, right
#     end
# end

def sum_of_left_leaves(root)
    return 0 unless root

    stack = [[root, false]]
    sum = 0

    until stack.empty?
        node, is_left = stack.pop
        if node.left.nil? && node.right.nil? && is_left
            sum += node.val
        end
        stack.push([node.right, false]) if node.right
        stack.push([node.left, true]) if node.left
    end

    sum
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode 
= null, _right: TreeNode = null) {
 */
object Solution {
  def sumOfLeftLeaves(root: TreeNode): Int = {
    if (root == null) 0
    else {
      var sum = 0
      if (root.left != null && root.left.left == null && root.left.right == null)
        sum += root.left.value
      sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right)
    }
  }
}

                                            
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Box<TreeNode>>,
//   pub right: Option<Box<TreeNode>>,
// }
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn sum_of_left_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn is_leaf(node: &Option<Rc<RefCell<TreeNode>>>) -> bool {
            match node {
                Some(n) => {
                    let n = n.borrow();
                    n.left.is_none() && n.right.is_none()
                },
                None => false,
            }
        }
        
        fn sum_left_leaves(node: &Option<Rc<RefCell<TreeNode>>>, is_left: bool) -> i32 {
            match node {
                Some(n) => {
                    let n = n.borrow();
                    if is_leaf(&node) && is_left {
                        n.val
                    } else {
                        sum_left_leaves(&n.left, true) + sum_left_leaves(&n.right, false)
                    }
                },
                None => 0,
            }
        }
        
        sum_left_leaves(&root, false)
    }
}

To solve this coding challenge, we need to compute the sum of all left leaves in a given binary tree. A left leaf is defined as a leaf node that is the left child of its parent. We will use a depth-first search (DFS) to traverse the tree and keep track of which nodes are left children.

Explanation

To solve this problem, we must traverse the binary tree and identify which nodes are left leaves. A leaf node is a node with no children. We will use a depth-first search (DFS) approach, which can be implemented both recursively or iteratively. Here’s a step-by-step breakdown of our approach:

Initiate a sum variable to keep track of the sum of left leaves.
Perform a depth-first search (DFS) starting from the root node.
Use a helper function in our DFS to:

Determine if the current node is a leaf node.
Check if it is a left child.
If it is a left leaf, add its value to the sum.

Continue the DFS for the left and right children of the current node, while keeping track of whether each child is a left child or not.
Return the sum once the entire tree has been traversed.

Detailed Steps in Pseudocode

Define a function
sumOfLeftLeaves

that takes the root of the binary tree as its parameter.
Initialize a variable
sum

to 0.
Define a nested helper function
dfs

that performs the depth-first search. This function will take two parameters: the current node and a boolean indicating whether the current node is a left child.
In the
dfs

function:

Return immediately if the node is
null

(base case).
Check if the current node is a leaf node (i.e., has no children).
If the node is a leaf and is a left child, add its value to
sum

.

Recursively call
dfs

for the left and right children of the current node, updating the boolean parameter to indicate whether the child is a left child.
In the main function, initiate the DFS process starting with the root node and a boolean value of
false

(since the root cannot be a left leaf).
Return the final value of
sum

.

Detailed Pseudocode with Comments

                                            
# Function to find the sum of left leaves in a binary tree
sumOfLeftLeaves(root):
    # Initialize the sum to 0
    sum = 0
    
    # Define the DFS function to traverse the tree
    dfs(node, isLeft):
        # If the current node is null, return
        if node is null:
            return
        
        # Check if the current node is a leaf node
        if node.left is null and node.right is null:
            # If the current node is a left leaf, add its value to the sum
            if isLeft:
                sum += node.val
            # Return because it's a leaf node
            return
        
        # Recursively call dfs for the left child with isLeft=True
        dfs(node.left, true)
        
        # Recursively call dfs for the right child with isLeft=False
        dfs(node.right, false)
    
    # Start DFS with the root node and isLeft=false
    dfs(root, false)
    
    # Return the final sum
    return sum

By following the above methodology, we ensure that we traverse every node in the tree. We specifically check if a node is a left leaf and add its value to our running total sum. This approach guarantees that all left leaves are accounted for in our final result.