In left-child right-sibling encoding, what does preorder on the encoded binary tree correspond to?

## The encoding Left-child right-sibling turns an arbitrary n-ary tree into a binary tree without changing the node count and without losing any information. Each node keeps exactly two references: - **left** = the node's *first child* - **right** = the node's *next sibling* A node with no children has a null left pointer; the last child in a sibling group has a null right pointer. The root's right pointer is null in a single tree (in a forest, the right chain of the roots is how you encode several trees as one binary tree — a small bonus of the representation). The transform is reversible: to recover a node's children, follow left once and then chase right pointers until null. Sibling order is preserved by the order of that chain, so nothing about the original model is lost. ## The preorder correspondence Binary preorder is: visit the node, walk left, walk right. Substituting the meanings of the pointers, that reads: visit the node, walk its first child's chain, then walk its own next sibling's chain. Unrolling the recursion at a node with children `c1 … ck`, the left walk emits `c1`'s entire subtree, then — because `c2` hangs off `c1`'s right pointer — `c2`'s entire subtree, and so on through `ck`. So the emitted sequence is: node, subtree of `c1`, subtree of `c2`, …, subtree of `ck`. That is exactly the n-ary preorder definition. This is why the encoding is genuinely useful and not just a curiosity: code written for the binary shape, with two fixed pointers and no collection allocation per node, produces the correct traversal for a tree of unbounded fanout. ## The less obvious one: inorder gives postorder Binary inorder is: walk left, visit the node, walk right. At a node with children `c1 … ck`, the left walk covers the sibling chain `c1 … ck` and, inductively, emits each one's *postorder*; then the node itself is visited; then the right walk continues with the node's own siblings. So the encoding's inorder emits `post(c1), …, post(ck), node` — the n-ary postorder. That correspondence is a satisfying thing to derive out loud and a fair senior-level probe. No such tidy story exists for level-order. The encoding's binary depth is not the original depth, so the encoding's levels mix nodes from many original tiers. If you need tiers, traverse the original shape or carry depth explicitly. ## What the encoding costs | Operation | Children-list node | Left-child right-sibling | |---|---|---| | Reach the i-th child | direct indexed access | follow left, then i-1 right links: O(i) | | Number of children | already known | O(k) walk, unless stored | | Add a child at the end | append to the list | O(k) walk to the chain's tail, or keep a tail pointer | | Add a child at the front | may shift elements | O(1) pointer splice | | Node memory | two-pointer header plus a growable collection | exactly two references, uniform | | Depth of the structure | equals the original height | original height plus preceding-sibling counts | The last row is the one people miss. Depth in the encoding grows with the number of siblings preceding a node along its path, so a two-level tree with a root and a thousand children encodes as a binary tree of depth one thousand. Anything whose cost tracks the binary structure's height — a recursive walk, a path-following operation — behaves very differently on the encoding than on the original. ## When the encoding is the right call It earns its place where a *uniform, fixed-size node* is worth more than random child access: nodes packed into a flat block with no per-node collection allocation, structures written into a compact file format, or an environment where allocating a growable list per node is the dominant cost. Two references per node is also a predictable memory footprint across millions of nodes, whereas a per-node collection carries its own header and slack. It is the wrong call when code frequently asks for "the third child", "how many children does this node have", or "the tiers of this hierarchy" — all cheap on a children list and all linear-in-fanout or worse on the encoding. It also costs readability: engineers reading `node.right` and thinking "second child" is a real and recurring bug, so a team adopting it should rename the fields to `firstChild` and `nextSibling` and let the two-pointer layout be an implementation detail rather than the mental model. ## Common misconceptions to avoid That the right pointer is a second child — it is a sibling, and reading it as a child scrambles the structure. That the encoded binary tree is a search tree — there is no ordering invariant on keys at all; the shape is a representation, not an index. That the encoding loses child order — it does not; the sibling chain *is* the order. And that a walk of the encoding costs the same as on the original in every respect — total traversal is still O(n), but per-node child access and structural depth are not comparable.