4
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ A Dyck path doesn't cross below the X axis, but ends on it. That's why its last step is always Down. $\endgroup$ – Yuval Filmus Mar 21 at 20:56
  • $\begingroup$ I know, but why will this algorithm based on constructing it from a tree also satisfy this property? $\endgroup$ – Rohit Pandey Mar 21 at 21:30
  • $\begingroup$ Can you explain how you assign keys to nodes? $\endgroup$ – Yuval Filmus Mar 21 at 21:32
  • $\begingroup$ Sorry, should have mentioned - the keys are from 1 to $n$ and there is only one way to label a BST with them. Editing the question. $\endgroup$ – Rohit Pandey Mar 21 at 21:34
  • 1
    $\begingroup$ cs.stackexchange.com/a/136257/683 $\endgroup$ – Yuval Filmus Mar 21 at 22:25
3
$\begingroup$

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}$.

enter image description here

$\endgroup$
2
  • $\begingroup$ is there a nice algorithm to traverse the tree like the picture in your second approach? $\endgroup$ – Rohit Pandey Mar 26 at 2:09
  • $\begingroup$ Sometimes this is called an Euler traversal of the tree. The first method is a kind of recursive implementation of the traversal (or an inductive definition, depends how you look at it). A natural nonrecursive implementation would be with a stack. During the traversal the stack contains the nodes of the path from the root to the visited node. I believe that is similar to the post-order traversal in wikipedia (en.wikipedia.org/wiki/Tree_traversal#Post-order) except that the node is "visited" at differerent steps in the code, just before moving to the left and right children. $\endgroup$ – Hendrik Jan Mar 26 at 9:43
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ In my opinion you are too pessimistic. The correspondence between binary trees and Dyck paths is well established. I tried to explain that your recursive function closely follows the recursion of the Dyck path for a binary tree. Your start variable accounts for the number of left branches, which equals the shift of the positions in the string. If those recursions match you do not need to reprove the properties for a bijection between trees and Dyck paths. $\endgroup$ – Hendrik Jan Mar 24 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.