Sum of Left Leaves LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple FacebookViews 1161

Problem Statement:

Sum of Left Leaves LeetCode Solution – 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 & Explanation:

Sum of Left Leaves LeetCode Solution

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.

 

Constraints:

Sum of Left Leaves LeetCode Solution

Observation:

  • Leaf node:  Nodes that have no left child and no right child.

                                                                     node==null

  • Left leaf node: Node that has left child and that left child has no right child and left child.

                                                     node.left != null and node.left.left==null and node.left.right == null

Approach:

  • We can use Post Order Recursive Traversal.
  • In postorder traversal, we are making faith that if we make a call to the left child of the root node then it will give us the sum of the all left leaves present in the left child, and so on, if we make a call to the right child of the root node then it will give us the sum of the all left leaves node present in the right child.

                                                                         int left=sumOfLeftLeaves(root.left);

                                                                        int right=sumOfLeftLeaves(root.right);

Algorithm:

As we know post order recursive traversal is a divide and conquer technique so if we manage all cases at the root node then when we will call to the left child and right child it will also be handled.

  • If the root is null then return zero.
  • Initialize a leftLeafValue variable with zero.
  • Make a recursive call on the left child and on the right child.

                                            int left = sumOfLeftLeaves (root.left);

                                            int right = sumOfLeftLeaves (root.right); 

  • Now suppose your root has the left leaf node then simply add the left node value in the leftLeafValue

                                            leftLeafValue +=  root.left.val;

  • At last return left + right+ leftLeafValue

Code

JAVA Code for Sum of Left Leaves

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

C++ Code for Sum of Left Leaves

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL)return 0;
        int leftLeafValue=0;
        int left=sumOfLeftLeaves(root->left);
        int right=sumOfLeftLeaves(root->right);
        if(root->left!=NULL&&root->left->left==NULL&&root->left->right==NULL)
               leftLeafValue+= root->left->val;
       
        return leftLeafValue+left+right;
    }
};

Complexity Analysis for Sum of Left Leaves LeetCode Solution

  1. Time Complexity: T(n) = O(n) Since we are visiting all n nodes
  2. Space Complexity: A(n) = O(1)  since we are not using any space except the recursive stack.
Translate »