0
$\begingroup$

How can it be proved that two different kinds of dfs ( for example let call them inorder and postorder) unequivocally define a unique tree? Let's say we have two dfs arrays:

A0(inorder) = {a01, a02, a03, ... a0n};
A1(postorder) = {a11, a12, a13, ... a1n};

So can we say that the pair {A0 and A1} defines a unique tree, if so how can we prove it?

$\endgroup$
5
  • $\begingroup$ What do you mean by that? What tree do you have in mind? How do those two results of DFS define a unique tree? What is meant by your notation? Do you only want to prove that for inorder and postorder, or for some more general statement? If more general, what is the formulation of the set of kinds of DFS you want to consider? What's the context where you encountered this question or the motivation? $\endgroup$
    – D.W.
    Nov 22 '21 at 9:16
  • $\begingroup$ Is my question so ambiguous? Given an N-ary tree (I haven't mentioned bst or something else means a general tree), also given two arrays: its inorder and postorder traversals A0 and A1. How to prove that the pair {A0, A1 } uniquely defines the tree. $\endgroup$
    – user37014
    Nov 22 '21 at 10:31
  • $\begingroup$ In the in-order visit are you visiting each non-leaf vertex $d-1$ times, where $d$ is the degree of that vertex? $\endgroup$
    – Steven
    Nov 22 '21 at 12:35
  • $\begingroup$ Steven - Each node is visiting only once $\endgroup$
    – user37014
    Nov 22 '21 at 13:49
  • $\begingroup$ Please don't add clarifications in the comments. Instead, please edit the question to clarify it, so it reads well for others who encounter this. We don't want people to have to read the comments to understand the question. Part of our mission is to build up an archive of high-quality questions and answers that will be useful to others in the future. I found it unclear -- I don't understand what "uniquely defines the tree" means; and you haven't answered my question about whether you are only asking about inorder+postorder or for other kinds of DFS as well. $\endgroup$
    – D.W.
    Nov 23 '21 at 4:37
2
$\begingroup$

Since your are talking about in-ordering, I will suppose that the tree is a binary tree (otherwise I don't know how the in-order is defined).

This result of unicity can be proven by induction of the length of arrays, but only if nodes are distincts (which I will assume for the rest of the proof). Suppose $T$ to be a tree with an in-order given by $A = (a_1, a_2, …, a_n)$ and a post-order given by $B = (b_1, …, b_n)$.

  • If $n = 0$, then the tree is the empty tree and is unique.

  • Suppose the result is true for all lengths of array $\leqslant n$, $n$ being a fixed non-negative integer. Let $T$ be a tree with an in-order given by $A = (a_1, a_2, …, a_{n+1})$ and a post-order given by $B = (b_1, …, b_{n+1})$.

    • Since $B$ is a post-order, that means there exists $k\in \{0,…, n\}$ such that $T = Node(b_{n+1}, T_l, T_r)$, and $T_l$ has a post-order $B_l=(b_1, …, b_k)$ and $T_r$ has a post-order $B_r = (b_{k+1}, …, b_{n})$.
    • Since $A$ is an in-order, that means that $T_l$ has an in-order $A_r=(a_1, a_2, …, a_k)$, $b_{n+1} = a_{k+1}$ and $T_r$ has an in-order $A_l=(a_{k+2}, …, a_{n+1})$. Since nodes are distincts, the equality $b_{n+1} = a_{k+1}$ guarantees a unique value of $k$.
    • Now, $T_l$ has in-order $A_l$ and post-order $B_l$, and since $|A_l| = |B_l| = k \leqslant n$, there exists (by induction hypothesis) a unique corresponding tree. The same way, there exists a unique possible $T_l$

    We conclude that there exists a unique tree $T = Node(b_{n+1}, T_l, T_r)$ with in-order $A$ and post-order $B$.

$\endgroup$

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.