binary code to encode binary tree

Question

I would like to encode a binary tree where every node has either 0 or 2 kids into a binary word.

I was thinking about marking every left edge with a "0" and every right edge with a "1" and then use every path from root to a leaf concatenated to encode the tree, but I'm not sure if this results in a unique code for every tree?

I thought about it for quite some time but I can not figure out... maybe you know?

Answer 1

First of all, let's consider that we are talking about labeled trees. Otherwise it will be difficult to find bijection between trees and binary strings.

Then we can traverse a given tree in-order (https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR)) and print $1$ each time, when we enter some vertex, and $0$ each time, when we leave some vertex.

Another possible encoding can be constructed in the following way. Let's enumerate all vertices by layers from root to bottom (and from left to right inside each layer). And then let's construct binary string of length $|V|$ where the $i$-th position is $1$ if the corresponding vertex has children and $0$ otherwise.