Leetcode Daily - August 24, 2020

Sum of Left Leaves

Link to Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - DFS

(Submission - Accepted)

When I see a tree problem like this, my go-to is DFS or BFS (I usually start with DFS by default), and I tend to use a stack (you can use recursion as well).

The principle is to simply check each node to find nodes that:

• Are leaves
• Were the left of their parent

Once a node is found that meets these conditions, I can simply add their value to a sum that is initialized to zero at the start of the program.

The only additional thing I really need is a data structure that tells the current node if it was the left or right of its parent (or root if it is root).

I implemented this with a dictionary (in Python) that stores the node, and 'nType', or node type. The node type is currently either 'root', 'right' or 'left'. I left the type as a string for the purposes of quickly submitting code, but an enum can be used since the data can only be one of a possible set.

Submitted Code (Python):

class Solution(object):
    def sumOfLeftLeaves(self, root):

        if root == None:
            return 0
        result = 0 
        stack = [{'node': root, 'nType': 'root'}]

        # dfs using a stack 
        # add to result if left and a leaf 
        # should add an additional data, whether it was left or right or root
        while len(stack) > 0:
            curr = stack.pop() 
            currNode = curr['node']
            currType = curr['nType']

            # check if leaf 
            if currNode.left == None and currNode.right == None and currType == 'left':
                result += currNode.val

            # add children to tree 
            if currNode.left != None:
                stack.append({'node': currNode.left, 'nType': 'left'})

            if currNode.right != None:
                stack.append({'node': currNode.right, 'nType': 'right'})

        # end of while loop
        return result 

Discussion and Conclusions

As mentioned in the approach section, a better data structure such as an enum could be used for storing the status of the current node. But my main concern for optimizing performance is whether I can consistently search less than O(n) (where n is the number of nodes in the tree) nodes.

I've been thinking about how to potentially rule out certain portions of the tree, but based on the node data structure I'm not sure that's feasible. Basically, since any node can have a left child, and each node points to its children but not its parents, we would have to check every node to make sure that it's not both left and a leaf node.