Writing a tree down and reading it back

The framing problem from Unit 1, now with structure instead of a flat list.

Why it works

Record the empty children

The previous lesson established that one traversal does not determine a tree. That is true of traversals that skip empty children. Once every absent child is written down explicitly, a single pre-order traversal does determine the tree.

The markers are what supply the missing information. They tell the reader exactly where each branch stops, which is the same job the length prefix did in Unit 1.

There is a cost, and it is worth knowing before you write anything. Every node has two child slots, so a tree of n nodes has exactly n plus 1 slots that are empty.

1for nodes in (1, 2, 4, 7):2    print(nodes, "nodes ->", nodes + 1, "markers ->", 2 * nodes + 1, "tokens in total")

Roughly half the output is markers, whatever the shape. That is the price of being unambiguous.

Why it works

Reading it back is the same traversal

The reader consumes tokens in the order they were written and rebuilds in the same pre-order shape. Take a token: if it is the marker, this branch is empty; otherwise make a node, then build its left subtree, then its right.

The recursion consumes exactly the tokens belonging to each subtree and leaves the rest, which is what makes the second call pick up in the right place. That property is the whole reason this works, and it is worth convincing yourself of by hand on a three-token stream before trusting it on a large one.

Everything rests on the position being shared, so watch that on its own before assembling anything.

1tokens = "1,2,#,#,3".split(",")2at = 03 4def take():5    global at6    token = tokens[at]7    at += 18    return token9 10print(take(), take(), take())11print("position is now", at, "so whatever runs next resumes at", tokens[at])

Three separate calls, one cursor. That is what lets two sibling recursions divide the tokens between them.

Predict the output· 5 min

Predict the output: with and without the empty markers

Two different trees are written down in preorder. One version records nothing for an absent child; the other writes a #. Type the four lines it prints.

Python

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def bare(node):6    if node is None:7        return []8    return [str(node.val)] + bare(node.left) + bare(node.right)9 10def marked(node):11    if node is None:12        return ["#"]13    return [str(node.val)] + marked(node.left) + marked(node.right)14 15left_leaning = T(1, T(2))16right_leaning = T(1, None, T(2))17 18print(",".join(bare(left_leaning)))19print(",".join(bare(right_leaning)))20print(",".join(marked(left_leaning)))21print(",".join(marked(right_leaning)))

Printed output

Problem· 35 min

Serialize And Deserialize Binary Tree

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1tokens = "1,2,#,#,3".split(",")2at = 03 4def take():5 global at6 token = tokens[at]7 at += 18 return token9 10print(take(), take(), take())11print("position is now", at, "so whatever runs next resumes at", tokens[at])

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def bare(node):6 if node is None:7 return []8 return [str(node.val)] + bare(node.left) + bare(node.right)9 10def marked(node):11 if node is None:12 return ["#"]13 return [str(node.val)] + marked(node.left) + marked(node.right)14 15left_leaning = T(1, T(2))16right_leaning = T(1, None, T(2))17 18print(",".join(bare(left_leaning)))19print(",".join(bare(right_leaning)))20print(",".join(marked(left_leaning)))21print(",".join(marked(right_leaning)))