Depth-first Unary Degree Sequence

The old Daily Coding Problem email list gave us this problem around 2020:

Daily Coding Problem: Problem #237 [Easy]

A tree is symmetric if its data and shape remain unchanged when it is reflected about the root node. The following tree is an example:

        4
      / | \
    3   5   3
  /           \
 9             9

Given a k-ary tree, determine whether it is symmetric.

This problem is less well described than I thought when I worked on it in 2020.

I did not see an implicit “all child nodes are non-nil” in the problem. I let every node of the “k-ary” trees have an arbitrary number of child nodes, and also have nil-valued child nodes.

As part of testing my solution to the problem, I wrote a parser for a lisp-like “balanced parentheses” string representation of k-ary trees. That way, I could try different trees rapidly.

Because I allowed unset child nodes, the k-ary tree of the coding problem could arguably be represented at least two ways:

  1. (4 (3 (9)) (5) (3 (9)))
  2. (4 (3 (9) ()) (5) (3 () (9)))

I chose data structures and wrote code that allows representing the same tree at least two ways because the problem description isn’t too precise.

Much later, October of 2025, almost exactly 5 years after git says I did the problem originally, I was looking around the web for succinct binary tree encoding information. I stumbled across a mention of a supposedly “well-known” text encoding of trees, “DFUDS”, Depth-first Unary Degree Sequence.

The reference was to:

D. Benoit, E. D. Demaine, J. I. Munro, R. Raman,
V. Raman, and S. S. Rao.
Representing Trees of Higher Degree.
Algorithmica, 43(4):275-292, 2005

It looks like DFUDS tree representation first appeared in:

Representing Trees of Higher Degree,
same authors,
Algorithms and Data Structures,
6th International Workshop, WADS ‘99, Vancouver, British Columbia, Canada, August 11-14, 1999, Proceedings

Benoit et al describe two subtly different kinds of “higher degree trees”. They call one kind “ordinal trees”, where each node can have different numbers of child nodes, but there’s no null children. The other kind, they call “cardinal trees”. Nodes in a cardinal tree have a fixed number of child nodes, but some or all child nodes’ fields can be nil or unset. Both types have child nodes in a fixed order.

Our friend the binary tree is a cardinal tree. Every node has up to two child nodes, either or both can be nil. The child nodes have a fixed order, usually left to right.

Tying this back to Daily Coding Problem: Problem #237 [Easy], my data structure for the problem’s trees is an unholy mixture of ordinal tree and cardinal tree. Allowing both nil child nodes and arbitrary numbers of child nodes ends up allowing multiple ways to represent the same tree as a string. I think this is why Benoit and company made a distinction between ordinal and cardinal trees, although they never say so.

DFUDS format is a little hard to describe. Even Benoit & Co. had trouble. Their example (Fig 1 of the conference paper) is difficult to understand.

Another paper, On Succinct Representations of Binary Trees, by Pooya Davoodi, Rajeev Raman and Srinivasa Rao Satti, describes creating a DFUDS representation by making a pre-order, depth first traversal of the tree. At each node, output one ‘(’ for each child node, then a ‘)’. Do the same for each child node.

Here’s an example tree for (0 (1) (2 (3) (4)) (5)). in my lisp-like string representation:

example k-ary tree, an ordinal tree, maybe

Constructing a DFUDS representation by Davoodi, Raman and Satti’s method:

  1. 0-valued node has 3 children, so it is represented as (((0)
  2. 1-valued node has no children, the string rep is 1)
  3. 2-valued node has 2 children, it becomes ((2)
  4. 3- and 4-valued nodes have no children, they are 3) and 4)`
  5. 5-valued node is 5)

The depth first traversal visits the nodes in the order of my list, so the DFUDS representation is almost

(((0) + 1) + ((2) + 3) + 4) + 5) → (((0)1)((2)3)4)5)

The parentheses don’t balance so put a ( prefix on it for ((((0)1)((2)3)4)5) There’s some handwaving about this prefix as a “superroot”. Just admit it’s there to balance, folks.

Comparing DFUDS and lisp-like, “Balanced Parens” representations:

  • ((((0)1)((2)3)4)5)
  • (0(1)(2(3)(4))(5))

DFUDS and Balanced Parens string representations without the values ("(((())(())))" and “(()(()())())” in the above examples) are words in a Dyck Language.

At least a few parentheses-only tree representation can be both DFUDS and Balanced Parens representations. A single node tree has “()” as a representation in either system. An ordinal tree consisting of a root and a single child is represented by “(())” in both systems. Strangely, a 3-node tree, grandparent-parent-child, has “(()())” as a DFUDS representation and “((()))” as a Balanced Parens representation.

There are some Dyck Words that don’t represent either DFUDS or Balanced Parens tree representations, like “()()”. All DFUDS and Balanced Parens representations have the outer pair of parentheses match.

My personal takeaway is that even something as obvious as the Balanced Parentheses, lisp-like representations aren’t the only possible representations.

Code repo for higher degree tree coding problems and other related curiosities.