Hi Codeforces!

This is a blog about a really cool folklore technique that seems to have been forgotten over time. I currently only know of one place where it is mentioned on the internet, https://www.algonotes.com/en/minimal-memory-dp/ (from 2018), but I've been told that it is far older than this. I don't know of a name for this technique, so I've decided to call it Xor Linked Tree because of its close connection to XOR linked lists https://en.wikipedia.org/wiki/XOR_linked_list .

This is a technique for solving tree problems using extremely little time/memory. For example, every fastest solution in the "Tree Algorithms" section on https://cses.fi/problemset/ currently uses this technique. So it is blazingly fast.

The idea:

Suppose in the input of a problem, you are given a tree as $$$n - 1$$$ edges. To construct the XOR Linked Tree data-structure from this, you go through the list of edges and store the following two things for every node in the tree:

1. deg[node] = The degree of the node.
2. xor[node] = The XOR of all neighbours of node.

Storing this will only take $$$2 n$$$ integers, so this is very cheap memory wise compared to an adjacency list. It is also much faster, since there are no expensive .push_back/.appends.

Claim: Using deg and xor, it is possible to reconstruct the tree.

Proof: Identify a leaf node in the tree (this can be done by finding a node with degree 1 in deg). Note that a leaf only has one neighbour, so the XOR of all of its neighbours is simply that neighbour. So the neighbour of a leaf is simply xor[leaf]. Now remove this leaf from the tree ("pluck it") by lowering the degree of its neighbour by one (deg[neighbour] -= 1) and XORing away leaf from xor[neighbour] (xor[neighbour] ^= leaf). Now we can just repeat this process of plucking leaves until there a single node left. We have now reconstructed the original tree.

Here is an implementation of the process described in the proof above ^

for node in range(n):
    while deg[node] == 1:
        nei = xor[node]

        # Pluck away node
        deg[node] = 0
        deg[nei] -= 1
        xor[nei] ^= node

        # Check if nei is now a leaf
        node = nei

Something to note is that it is possible to control which node is left at the end (the "root") by setting its degree to 0 before running the algorithm. So the final XOR Linked Tree traversal algorithm is

deg[root] = 0
for node in range(n):
    while deg[node] == 1:
        nei = xor[node]

        # Pluck away node
        deg[node] = 0
        deg[nei] -= 1
        xor[nei] ^= node

        # Check if nei is now a leaf
        node = nei

This is it! This is the entire algorithm.

Discussion

This tree traversal algorithm is very different from any other traversal algorithm, like DFS or BFS. For one, it doesn't use anything like a queue or a stack. Instead it simply removes one leaf using a while loop inside of a for loop. The order you traverse the nodes in is kind of like doing a BFS in reverse, but it is not exactly the same thing.

Discussion (Advanced)

One last thing I want to mention is that on some tree problems, you need specifically need a DFS ordering. For example, there are tree problems on cses.fi that requires you to compute LCA. Most if not all algorithms/data-structures for computing LCA is based on DFS. So does that mean that it is not possible to use XOR Linked Tree traversal algorithm for those problems?

The answer is no. It is possible to use the XOR Linked Tree traversal algorithm to compute a DFS ordering. The trick is first compute subtree sizes, and then use those to compute where in a DFS ordering each node should be.

TODO