Java iterative and recursive solutions

• Recursive method. For given node we check whether its left child is a leaf. If it is the case, we add its value to answer, otherwise recursively call method on left child. For right child we call method only if it has at least one nonnull child.

``````public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int ans = 0;
if(root.left != null) {
if(root.left.left == null && root.left.right == null) ans += root.left.val;
else ans += sumOfLeftLeaves(root.left);
}
ans += sumOfLeftLeaves(root.right);

return ans;
}
``````

Iterative method. Here for each node in the tree we check whether its left child is a leaf. If it is true, we add its value to answer, otherwise add left child to the stack to process it later. For right child we add it to stack only if it is not a leaf.

``````public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int ans = 0;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);

while(!stack.empty()) {
TreeNode node = stack.pop();
if(node.left != null) {
if (node.left.left == null && node.left.right == null)
ans += node.left.val;
else
stack.push(node.left);
}
if(node.right != null) {
if (node.right.left != null || node.right.right != null)
stack.push(node.right);
}
}
return ans;
}
``````

• @yerkezhan For the recursive solution, you don't need to check (root.right.left != null || root.right.right != null) along with if(root.right != null)

• @mashfique thanks! You are right, I updated my post

• @mashfique Could you explain why?

• @Yoly0412 For the recursive solution, if node.right != null , we don't need to check if node.right is a leaf or not. We can just make a recursive call on node.right and keep on traversing the tree.

• My version. A little bit cleaner.

``````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;
} else {
sum += sumOfLeftLeaves(root.left);
}
sum += sumOfLeftLeaves(root.right);
return sum;
}
}
``````

• I came up with a more straightforward way to solve this problem, a little bit like the recursive way above. Instead of do it in the original function, I traverse the tree in inOrder sequence but with the tree side information.

``````int sum;
public int sumOfLeftLeaves(TreeNode root) {
sum = 0;
inOrder(root, false); // false means the next node is not in the left side.

return sum;
}

private void inOrder(TreeNode root, boolean left) {
if (root == null) {
return;
}

inOrder(root.left, true); // true means the next node is in the left side.
if (root.left == null && root.right == null && left) { // only left leaves can be added to result;
sum += root.val;
}
inOrder(root.right, false);
}``````

• You don't need the if(root.right != null) check.

• @yfcheng you are right! Thanks! Because at the beginning of the method I already check
`if(root == null)`

• ``````public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
int sum = 0;
if(root == null){
return 0;
}
Stack<TreeNode> stack = new Stack();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
sum += getLeftLeafValue(node);
if(node.left != null)
stack.push(node.left);
if(node.right != null)
stack.push(node.right);
}
return sum;
}

int getLeftLeafValue(TreeNode root){
if(root != null && root.left != null && (root.left.left == null && root.left.right == null)){
return root.left.val;
}
return 0;
}
}
``````

• ``````public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
int sum = 0;
if(root == null){
return 0;
}
sum += getLeftLeafValue(root);
sum += sumOfLeftLeaves(root.left);
sum += sumOfLeftLeaves(root.right);
return sum;
}

int getLeftLeafValue(TreeNode root){
if(root != null && root.left != null && (root.left.left == null && root.left.right == null)){
return root.left.val;
}
return 0;
}
}
``````

• Is the time complexity in both cases O(n)?

• My recursive version

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

}
}
``````

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int SumOfLeftLeaves(TreeNode root) {
return sum(root, false);
}

private int sum(TreeNode root, bool isLeft)
{
if(root == null)
return 0;
if(root.left == null && root.right == null)
if(isLeft)
return root.val;
else
return 0;
return sum(root.left, true) + sum(root.right, false);
}
}``````

• My preorder iterative solutions:

``````public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
int sum = 0;
while(curr != null || !stack.isEmpty()) {
if (curr != null) {
if (curr.right != null)
stack.push(curr.right);
curr = curr.left;
if (curr != null && curr.left == null && curr.right == null) {
sum += curr.val;
}
} else {
curr = stack.pop();
}
}
return sum;
}``````

• @ZhuEason Have same idea as yours perhaps because it is more intuitive as you said.

``````    public int sumOfLeftLeaves(TreeNode root) {
return dfs(root, null);
}

private int dfs(TreeNode root, TreeNode pre) {
if (root == null) return 0;
if (root.left == null && root.right == null)
return (pre != null && pre.left == root) ? root.val : 0;
return dfs(root.left, root) + dfs(root.right, root);
}
``````

But this "look ahead" approach is also very nice.

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

• if (node.right.left != null || node.right.right != null) can be omitted.

• @cdai This one makes more sense to me. It's straight forward.

• @yfcheng and @yerkezhan :
RE: Why remove
if (root.right != null)
before calling the method on the right node? Sure, you don't have to have the check because the recursion method has a base case, but is it faster to call the method again and immediately exit on a base case? Why not avoid another call with a simple check? It doesn't seem to be faster and my smoke test didn't indicate that. Also, you're not even saving a check, you're simply doing it after another method call. It seems unnecessary. Do you know why one approach is better than the other? I don't, but I assume your reasoning is less typing/cleaner. Thanks for answering!

• @yerkezhan Here's a simple method that doesn't use any global variables:

``````    public int sumOfLeftLeaves(TreeNode root) {
return helper(root, false);
}

private int helper(TreeNode root, boolean isLeft) {
if (root == null) return 0;
if (root.left == null && root.right == null && isLeft) {
return root.val;
}
return helper(root.left, true) + helper(root.right, false);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.