Java iterative and recursive solutions


  • 58
    Y

    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;
    }
    

  • 3
    A

    @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)


  • 0
    Y

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


  • 0
    Y

    @mashfique Could you explain why?


  • 0
    A

    @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.


  • 9
    D

    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;
        }
    }
    

  • 2
    Z

    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);
    }

  • 0
    Y

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


  • 0
    Y

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


  • 1
    C
    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;
        }
    }
    

  • 1
    C
    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;
        }
    }
    

  • 0
    S

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


  • 6
    Y

    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); 
           
        }
    }
    

  • 2
    J
    /**
     * 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);
        }
    }

  • 0
    D

    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;
    }

  • 2

    @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);
        }
    

  • 0
    C

    said in Java iterative and recursive solutions:

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


  • 0
    A

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


  • 0
    J

    @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!


  • 2

    @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);
        }
    

Log in to reply
 

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