Another standard problem for tree recursion.
function sumTheTreeValues(root){
if (!root) { return 0}
let a = sumTheTreeValues(root.left)
let b = sumTheTreeValues(root.right)
return a + b + root.value
}All posts by Aaron
Pre/In/Post-Order Tree Traversal (Leetcode 20)
These don’t need to be 3 different questions. The vocabulary (knowing what pre, in, post means) is nice, and the questions follows what I see as the “typical” recursive tree-problem skeleton.
The first one is how I think it should be solved (albeit recursively). If memory serves, doing it iteratively for infix is a bit interesting. The other two example solutions are very terse.
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root is None: return []
prefix = self.preorderTraversal(root.left)
suffix = self.preorderTraversal(root.right)
return [root.val] + prefix + suffixclass Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)Vclass Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root is None: return []
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]Tree to list (Code Wars 21)
Breadth-first search! Of an arbitrary (not necessarily binary) tree. Glad to have this one. At least in the python implementation it’s weird that they model null as [], it should be None, but whatever.
def tree_to_list(tree_root):
res = []
worklist = [tree_root]
while worklist:
n = worklist[0]
worklist = worklist[1:]
if n == []:
continue
res.append(n.data)
for c in n.child_nodes:
worklist.append(c)
return resBinary Tree Search (Code Wars 20)
This is probably the right “intro to trees” question I’ve been looking for. The previous one I’ve been doing, “print everything in a binary tree”, is a bit too clunky. For those, people get hung up on the fixation with in-order versus pre-order or whatever, and also the problems usually model it as return an array of the visited nodes; and so they want to pass that as an out-parameter or similar. Ugh!
So I like this better.
def search(n: int, root: Optional[Node]) -> bool:
""" Determines if a value is in a binary tree (NOT bst) """
if root is None:
return False
if root.value == n:
return True
return search(n, root.left) or search(n, root.right)Normalize Array Indexes (Code Wars 19)
This was a problem a student brought to me. It was very interesting! It suggests 2 approaches of different “trickiness”.
The natural approach suggested by the problem’s description is to use a for-loop. This is complicated by that, in an unusual twist, the for loop (over the provided index parameter) isn’t really related to the length of the array. So while you have the i or whatever in your for loop, you want to resist the temptation to do a[i].
Ultimately you’ll want a secondary variable. While i tracks the provided index, j handles the “wrap-around” logic:
def norm_index_test(seq, ind):
if seq == []:
return None
isneg = ind < 0
ind = abs(ind)
j = 0
for i in range(ind):
j += 1
if j == len(seq):
j = 0
assert(j < len(seq))
if isneg and j != 0:
j = len(seq) - j
return seq[j]This is actually probably the hardest form of the question, complicated by the negative indexes. If I were asking this problem, I would not ask about negative indexes. Ugh!
Once you can trust modular arithmetic (and maybe Python makes it too easy? Not sure if all languages define module of a negative number the same), it’s a one-liner. Cute, but OK.
def norm_index_test(seq, ind):
if seq == []:
return None
return seq[ind%len(seq)]RLE compress string (Leetcode 19)
OK, a sequel!
I like:
- We have two views of the same array.
- We can start at 1 in the for-loop
- Opportunity for invariants to help our loop-based reasoning.
- Things get much simpler with the helper function (i.e., I made a lot of bugs until I decided to use a helper function).
I don’t think I’m biased to say this one requires a bit of careful thought!
class Solution(object):
def commitLetter(self, chars, c, i, count):
assert(count > 0)
chars[i] = c
i += 1
if count > 1:
w = str(count)
for t in w:
chars[i] = t
i += 1
return i
def compress(self, chars):
if len(chars) == 0: return []
count = 1
j = 0
lastChar = chars[0]
for i in range(1, len(chars)):
if chars[i] == lastChar:
count += 1
else:
j = self.commitLetter(chars, lastChar, j, count)
lastChar = chars[i]
count = 1
j = self.commitLetter(chars, lastChar, j, count)
return jDecompress RLE (Leetcode 18)
Another experiment: can leetcode-esque problems provide a useful way to learn computer science topics?
This problem is about run-length-encoding. Still pretty algorithmic, but a bit more applied. Though, as I did it, it really did feel more like understanding the description more than solving the problem. On the other hand, I think this is a great “fundamentals” problem.
class Solution(object):
def decompressRLElist(self, nums):
res = []
for i in range(0, len(nums), 2):
freq = nums[i]
val = nums[i+1]
res += freq*[val]
return resPath Finder 3 (Code Wars 18)
OK this series is winning me over. Cost function is just interesting enough.
def neighbors(maze, i, j):
toTry = []
if i > 0:
toTry.append((i-1, j))
if j > 0:
toTry.append((i, j-1))
if i + 1 < len(maze):
toTry.append((i+1, j))
if j + 1 < len(maze[i]):
toTry.append((i, j+1))
return toTry
def path_finder(maze):
maze = maze.split()
cost = {}
toVisit = set([(0,0)])
cost[(0,0)] = 0
target = (len(maze)-1, len(maze)-1)
while toVisit:
i, j = toVisit.pop()
c = cost[(i, j)]
for (a, b) in neighbors(maze, i, j):
d = abs(int(maze[i][j]) - int(maze[a][b])) + c
if (a, b) not in cost:
cost[(a, b)] = d
toVisit.add((a, b))
elif cost[(a, b)] > d:
cost[(a, b)] = d
toVisit.add((a, b))
if target in cost:
return cost[target]
return FalsePath Finder 2 (Code Wars 17)
I like the idea of a series. I suppose this is a nice-enough warm up to Djiskstra.
def neighbors(maze, i, j):
toTry = []
if i > 0:
toTry.append((i-1, j))
if j > 0:
toTry.append((i, j-1))
if i + 1 < len(maze):
toTry.append((i+1, j))
if j + 1 < len(maze[i]):
toTry.append((i, j+1))
final = [(a, b) for (a, b) in toTry if maze[a][b] == '.']
return final
def path_finder(maze):
maze = maze.split()
for row in maze:
assert(len(row) == len(maze))
cost = {}
toVisit = set([(0,0)])
cost[(0,0)] = 0
target = (len(maze)-1, len(maze)-1)
while toVisit:
i, j = toVisit.pop()
c = cost[(i, j)] + 1
for (a, b) in neighbors(maze, i, j):
if (a, b) not in cost:
cost[(a, b)] = c
toVisit.add((a, b))
elif cost[(a, b)] > c:
cost[(a, b)] = c
toVisit.add((a, b))
if target in cost:
return cost[target]
return FalsePath Finder 1 (Code Wars 16)
Variation on island finding. Which is to say, more depth-first-search. Embarrassingly, I forgot some the base case!
def neighbors(maze, i, j):
toTry = []
if i > 0:
toTry.append((i-1, j))
if j > 0:
toTry.append((i, j-1))
if i + 1 < len(maze):
toTry.append((i+1, j))
if j + 1 < len(maze[i]):
toTry.append((i, j+1))
final = [(a, b) for (a, b) in toTry if maze[a][b] == '.']
return final
def path_finder(maze):
maze = maze.split()
for row in maze:
assert(len(row) == len(maze))
seen = set([])
toVisit = [(0,0)]
seen.add((0, 0))
target = (len(maze)-1, len(maze)-1)
while toVisit:
i, j = toVisit.pop()
for (a, b) in neighbors(maze, i, j):
if (a, b) in seen:
continue
seen.add((a, b))
toVisit.append((a, b))
return target in seen