Tree DFS

[darwinrlo]

Sum of Path Numbers

• The function has a parameter, currNumber, that contains the current state of the number we're building along the root-leaf path. At the leaves, currNumber becomes the number associated with the root-leaf path and is returned.
• The function returns the sum of the leaves of the tree at the node.

Missteps

• There is a parameter, currNum, that contains the number so far. To iterate on the number at a node, currNum is multipled by 10 and the value of the node is added to it. I had forgotten to do this in the base case -- I simply returned currNum as it was passed in.
• I was just throwing away the return values of the recursive calls. I needed to assign them to variables and add them up.
• I think I was just tired. It seems that my performance in the late evening sucks.

Areas of Improvement

• The Grokking solution makes a recursive call for each child whether or not they are None. This is facilitated by the function returning 0 if the node passed in is None. What I was doing was checking each child pointer for None and recursing on that child if it wasn't None.

[darwinrlo]

Path With Given Sequence

Observations

• Returning False on a null node and a non-empty sequence allows me to recurse on a child without checking for None.
• My approach was to compare the node's value with the head of the list and then to pop the list before passing it to recursive calls. Grokking's approach is to use a pointer to keep track of the current element in the sequence. These are two different ways of doing the same thing.

Missteps

• I caught this in testing, but in the initial implementation, which I felt fairly confident in, I failed to handle the following cases:
  • The input sequence is empty. Either it was empty initially or all elements have been depleted. If the sequence is empty and there are still nodes left to go along the root-leaf path, then False should be returned.

Complexity

In the worst case, the binary tree is a linked list, the input sequence is as long as there are nodes, and it's a match. Since we're using recursion, a stack frame is allocated for each node. So the space complexity is O(n).

We may not visit every node, but in the worst case, we would visit every node, making the time complexity O(n).

Next Steps

• Look at each parameter and think about when each is 0, equal to the length of the list, empty, or None.
• Continue to work on thinking of test cases. Try to make sure each branch is exercised by the tests.