# How can it be proved that two different kinds of dfs unequivocally define a unique tree?

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?

• 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?
– D.W.
Nov 22 '21 at 9:16
• 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. Nov 22 '21 at 10:31
• In the in-order visit are you visiting each non-leaf vertex $d-1$ times, where $d$ is the degree of that vertex? Nov 22 '21 at 12:35
• Steven - Each node is visiting only once Nov 22 '21 at 13:49
– D.W.
Nov 23 '21 at 4:37

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