Sum of Left Leaves Leetcode Solutions

In this problem, we have to find the sum of all left leaves in a binary tree. A leaf that is called a "Left Leaf" if it is a left child of any node in the tree.

 

Example

2

 

/

 

4 7

 

/

 

9 4

Sum is 13

2

 

 

 

3

Sum is 0

Approach

We can use recursion to traverse the binary tree. If any node has a left child and it is a leaf too, we can add the value of the left child to our sum. But this approach uses the recursive stack space.

 

Can we use any other traversal that can save the memory space?

 

Morris Inorder Traversal can be implemented to visit every node iteratively. Check if it has a left leaf child and add its value accordingly in the result. This is the optimal approach. Note that we can implement "Morris Inorder traversal" only if the problem allows us to change the structure of the tree.

Algorithm(Recursive)

 

- Create a function sumOfLeftLeaves() that returns the sum of left leaves of any passed root

- If the root of the tree is NULL

 

- return zero

 

- If the current root has a left child and it is a leaf

 

- return its value + sumOfLeftLEaves(root->left) + sumOfLeftLeaves(root->right)

 

- Return sumOfLeftLEaves(root->left) + sumOfLeftLeaves(root->right)

 

Algorithm (Morris Inorder)

 

- Traverse the binary using Morris Inorder Traversal:

 

- Thread the inorder predecessor of the left subtree of any node to itself.

 

www.tutorialcup.com/leetcode-solutions/sum-of-left-leaves...

Done