I felt like it was time to knock some of these tree questions out. I find that solving tree questions in Python leads to simple, elegant code.

I went over Heap's Algorithm for solving permutation problems earlier. It hasn't fully *clicked* with me yet though. More studying is required -- as well as checking out alternative solutions. Heap's feels a little heavy-handed to me.

- Invert Binary Tree

Problem: Invert a binary tree.

I like the check I use here before I invert -- `if node.left or node.right:`

. It's instantly obvious that it will work for all three siutations, two leafs, one leaf, None.

# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object):def invertTree(self, root):""":type root: TreeNode:rtype: TreeNode"""def recurse(node):if node.left or node.right:node.left, node.right = node.right, node.leftif node.left:recurse(node.left)if node.right:recurse(node.right)returnif root:recurse(root)return root

This problem is a little bit of a meme. I expected it to be harder than it was but I have been revising tree algorithms recently..

Runtime complexity: `O(n)`

.

Spacetime complexity: `O(n)`

.

- N-ary Tree Postorder Traversal

Problem: Return the postorder traversal of a tree's values.

To think about this in another way, return the values as you would read the tree from the bottom up line by line.

"""# Definition for a Node.class Node(object):def __init__(self, val, children):self.val = valself.children = children"""class Solution(object):def postorder(self, root):""":type root: Node:rtype: List[int]"""vals = []queue = []if root:queue.append(root)while queue:cur = queue.pop()vals.append(cur.val)queue.extend(cur.children)return vals[::-1]

I recently learned (or, confirmed) that Python doesn't create new memory when slicing or creating an iterator, e.g. `[1,2][::-1]`

/ `reversed([1,2])`

. It seems obvious now that I think about it.

Runtime complexity: `O(n)`

.

Space complexity: `O(n)`

.

- N-ary Tree Preorder Traversal

Problem: Return the preorder traversal of a tree's values.

Another way to think about preorder traversal is Depth-First-Search order.

"""# Definition for a Node.class Node(object):def __init__(self, val, children):self.val = valself.children = children"""class Solution(object):def preorder(self, root):""":type root: Node:rtype: List[int]"""dfs_order = []def recurse(node):dfs_order.append(node.val)if node.children is not None:for i in range(0, len(node.children)):recurse(node.children[i])if root:recurse(root)return dfs_order

I think this is a fairly terse but understandable solution but you can only make DFS so complicated.

Runtime complexity: `O(n)`

.

Spacetime complexity: `O(n)`

.