Why does my code work: bijecting binary trees to Dyck paths

Question

The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan numbers. Another set of objects that follows the Catalan numbers is the number of binary search trees with $n$ nodes.

This suggests we can biject binary trees to Dyck paths (see here). We get a hint on how to do the bijection based on why the two objects satisfy the same recurrence (for Catalan numbers):

$$C_{n+1} = \sum\limits_{j=0}^{n}C_{j}C_{n-j}$$

Binary trees satisfy it because you designate one node as the root, then create a binary tree on its left (with $j$ nodes) and another one on its right. Dyck paths satisfy it by conditioning on the first time the path hits the y=0 line (which is what $j$ in the equation above represents). So we first take a mandatory step up, then we make a path of $2j$ steps that doesn't cross the $y=1$ line; then we go down one step to touch $y=0$ for the first time, and finally we make another path of $2(n-j)$ steps that doesn't cross the $y=0$ line.

This suggests we might be able to construct a Dyck path given a binary search tree (with node-keys labelled from $1$ to $n$ and there is just one way to assign them, see here) recursively, starting at the root. When we go to the left node of the tree, we need to consider the sub-path one level above the current level (where we start at level-0) and when we go to the right, we simply stay at the same level. Since the key of the node we're processing tells us where the path first struck the current level from the start, we know that it 2 times the number of steps representing the key from the start must be a step down.

The Python code below demonstrates this idea and works (tested it extensively). If you don't use python, the idea is very simple; I just set the path array to all 1's ("up" steps) and the recurse on the tree, inserting -1's ("down" steps) based on the keys on the tree nodes.

import numpy as np

class TreeToDyck():
  def __init__(self, tree_node, n):
    # Initially create an array of 2n ones. All steps are set to "up".
    self.path = np.ones(2*n)
    # Now insert downs at appropriate places.
    self.tree_to_dyck(tree_node, 1)

  def tree_to_dyck(self, tree_node, start):
    if tree_node is None:
        return
    # Go down. Bear in mind the "path" array is 0-indexed.
    self.path[start+2*tree_node.key-2] = -1
    self.tree_to_dyck(tree_node.left, start+1)
    self.tree_to_dyck(tree_node.right, start)

Now, the thing to note is that the key of the node we're at gives us many hints about the path. But, I ignore most of them and simply insert a "down" step. I start with all steps in the path array set to go up. Then, based on the keys of the tree nodes, I insert down steps.

Surprisingly, this is enough. Which means the following two statements must be true:

1. The down steps will never collide with each other. So, we'll never insert a "down" step at the same location twice. This will ensure we insert $n$ down steps, as the path must contain.
2. The last step in the Dyck path is always a "down" step. So, we will always end up inserting a "down" at the very last position in the array no matter the tree.

I want help proving the above two statements. And if there is any other requirement needed to prove that the algorithm will work.

Answer 1

My answer is not a formal proof, but I hope it contains enough information to make you feel confident about your own solution. My strings start at $1$. Sorry, old habit.

Consider a binary tree $T$ with $n$ nodes. Assume $T$ has $n$ nodes, subtrees $T_\ell$ and $T_r$. If the root of $T$ has label $k$ this means that $T_\ell$ has $k-1$ nodes.

A tree with $n$ nodes has a Dyck codes of length $2n$. There are two ways of determining the Dyck code $dyck(T)$ of tree $T$. One is recursively:

$dyck(T) = U \; dyck(T_\ell) \; D \; dyck(T_r)$.

In this string we observe exactly one $D$, which is associated to the tree $T$, other $D$'s are written recursively. The position of this single $D$ is exactly at $2k$. We know this because the length of $dyck(T_\ell)$ equals $2(k-1)$.

Note that the symbols generated by $dyck(T_\ell)$ are shifted by one, because of the $U$ that is written before its code. This is the main observation: it is due to a left branch, and those left branches is what you are counting in your code.

The other way of determining $dyck(T)$ is graphical. Draw the tree and make a traversal around it. Write $D$ for a left child (even when that leads to an empty subtree) and $U$ for a right child. (We visit each node twice: this is both an pre-order and inorder-traversal.) If you try this you will see that each $D$ appears at the number of the node plus the number of times we went left as seen from the root.

The tree below has code (with subscripts that count position in the string and superscript which is the inorder label associated to the root of the corresponding subtree) $U_1^3 U_2^1 D_3^1 U_4^2 D_5^2 D_6^3 U_7^{10} U_8^6 U_9^4 D_{10}^4 U_{11}^5 D_{12}^5 D_{13}^6 U_{14}^8 U_{15}^7 D_{16}^7 D_{17}^8 U_{18}^9 D_{19}^9 D_{20}^{10} U_{21}^{11} D_{22}^{11}$.

Answer 2

To formally prove my algorithm works, I think it is sufficient to show these three things. I haven't managed to prove all of them, but still leaving this as an incomplete answer and hope to fill in the gaps over time. Would appreciate if people can help fill the blanks of course.

1. In any path created from a valid BST using the algorithm in my question, there will be exactly $n$ tails.
2. Any path produced in this way is a valid Dyck path.
3. No two distinct trees can ever produce the same path.

For #1, its clear that there can't be more than $n$ tails since there are $n$ nodes in the tree and each of them insert one tail. The only way there can be less than $n$ tails is if two of the nodes insert tails into the same position. This is obviously true for all nodes which are reached by going only right from the root since they simply insert a tails at $2k$ where $k$ is their key. Because no two nodes can have the same key, their inserted tails won't collide with each other either.

When we go left, this is less clear; leaving incomplete for now.

For #2, we know that all Dyck paths end with a tails. And if there are $n$ nodes, there will always be a node with key $n$. And this node can only be possibly reached by going right from the root given the BST property. So, it'll always end up inserting a tail at toss # $2n$. Of course, this is not sufficient to prove that the path will be valid Dyck leaving the rest as TODO.

For #3, haven't been able to make progress so far, leaving it as a TODO.