Tree Certificate

PAL Certifikát Stromu

Build certificate

Assign string 01 to each node.
While (number of vertices is higher than 2) {
	For each non-leaf vertex {
		Remove inital 0 and trailing 1 from x's label
		
		// add labels of x and all the leaves to list
		labels = [ label[x] ]
		for each leaf l adjacent to x:
			labels.append(label[l])
			remove l from graph;
		
		// sort lexicographically
		labels = labels.lexiographicall_sort()
		
		// set new string for x
		label[x] = 0 + concat + 1
	}
}

if(only vertex x left){
	return label[x]
}
else(vertex x and y left){
	return concat(lex_sort(label[x], label[y]))
}

Build tree from certificate

root = node()
|V| = |Cert| / 2 // there are as man 0 as 1

node = root
foreach char c in the Cert[1]..Cert[-2]:
	if c == 0:
		// append new node to the current node
		new_node = node()
		parent[new_node] = node
		node.children.append(new_node)
		node = new_node
	else:
		// return to parent
		node = parent of node