A tree in memory is nodes and pointers. To save it to a file or send it over a network you flatten it into a string, and later rebuild the same tree from that string. A preorder walk that writes # for every empty child does both jobs in one pass each.
Visit a node, write its value, then serialize its left subtree and its right subtree. Whenever the walk reaches an empty child, write #. Each call adds exactly one token to the output, and the dashed squares on the drawing are the empty child slots waiting for their #.
How to read this: The walk visits each node top-down, left before right, and writes what it sees into the row below. Each small # square is an empty spot that also gets written.
Try this: Pick Left chain and count the # marks: always one more than the number of nodes.
Each of the n nodes has two child slots, 2n slots in all. Every node except the root sits in exactly one slot of its parent, so n − 1 slots hold nodes and the other n + 1 are empty. Each empty slot writes one #.
The markers tell a reader where every subtree stops. Without them the string 1,2,3 fits five different trees, as Lab 3 shows.
Reading runs the same recursion. A pointer moves left to right through the tokens. A number makes a node and then builds its left and right children, and a # returns an empty child. Edit the string to see how a broken one fails. The call stack is the same idea as in 005 · Recursion & fractals.
How to read this: The highlighted token is where the reader is. Each number makes a node; each # closes an empty spot. Red marks where a broken string fails.
Try this: Press Too few and Too many and watch where the red appears.
Each call consumes exactly one token and recurses in the same order the writer did, so the reader stops at the same boundaries the writer marked. A string is valid exactly when the root's call returns on the last token. Running out first means too few tokens, and leftovers mean too many.
Tree A is your tree. Tree B has a different shape but the same preorder sequence of values, so preorder alone cannot tell them apart. The null markers, the level order and the inorder sequence all can. Step through B to watch preorder plus inorder pin down one tree.
How to read this: Both trees list their values in the same order top-down, yet have different shapes. The tree with the green title is the one being rebuilt step by step.
Label any shape in preorder with the same values and its preorder comes out identical, so a bare preorder list fits C(n) trees: 1, 2, 5, 14, 42, 132, 429 for n = 1 to 7.
Preorder names each subtree's root first. Inorder lists everything left of that root before it and everything right of it after. With distinct values the root appears once in the inorder slice, so every split is forced. With repeats it breaks: 1,1 is both the preorder and the inorder of a root with a left child, and of a root with a right child.
Level order with nulls is the format LeetCode uses. It walks the tree breadth first, as in 002 · Graphs, and trims the nulls at the end. It is short for bushy trees and long for chains.