Sum of Left Leaves(Day14)

Problem statement:

Sum of 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.        

Intuition:

we have two traversal methods DFS and BFS, and here we will use preorder traversal.

1. 1. Start at the root of the binary tree.
2. 2. Check if the current node has a left child:

a. If it does, recursively visit the left child by calling the function with true indicating it's a left call.

b. If the left child is a leaf node (i.e., both its left and right children are null), return true.

3. If the current node is a right call (i.e., passed false), return false to indicate that it's not a perfect left-leaf node.

4. Check if the current node has a right child: a. If it does, recursively visit the right child by calling the function with false indicating it's a right call. b. If the right child is a left-leaf node, return true.

5. If none of the above conditions are met, return false.

6. Repeat this process for all nodes in the tree until all left-leaf nodes are found.

Code:

/**
 * 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;
        }
        return getSum(root,false);
    }
    public int getSum(TreeNode root, boolean isLeftChild){
        if(root.left==null && root.right==null){
            return (isLeftChild)?root.val :0;
        }
        int sum=0;
        if(root.left!=null){
            sum += getSum(root.left, true);
        }
        if(root.right!=null){
            sum += getSum(root.right, false);
        }
        return sum;
    }
}        

Time complexity: O(N) because we are traversing each node.

Space complexity: O(N) using recursion stack space.