# Find if a sequence of node is a result of a binary tree preorder traversal

Assume we have a sequence of 0's and 1's: $n_0, n_1, ..., n_N$, in which 0 stands for a leaf node, and 1 stands for an uncertain node (it may or may not be a leaf node). How to check if this sequence is a valid result of a binary tree preorder traversal?

Ex. $1, 1, 0, 1, 1, 0, 0, 1$ is a valid sequence.

• Starts with a zero and continues: invalid. More than $\lceil N/2\rceil$ zeroes: invalid. – greybeard Dec 20 '18 at 16:14

### Idea of a tree construction

If the length of the sequence is $1$ then just make the first symbol root and stop with SUCCESS. If the first symbol of the sequence is $0$ then construction is not possible, otherwise make it the ROOT and set the root to the ROOT.

for i = 2 to n
if n[i] is 1 then
if root.left is free
root.left = make_node(n[i])
root = root.left #go to left
else if root.right is free then
root.right = make_node(n[i])
root = root.right #go to right
else
# backtrack until root.right is free or we reach the ROOT - highest node
root = root.parent until root is nil OR root.right is free
end
else if n[i] is 0 then
if root.left is free
root.left = make_node(n[i])
else if root.right is free
root.right = make_node(n[i])
else
# backtrack until root.right is free or we reach the ROOT - highest node
root = root.parent until root is nil OR root.right is free
end
end

if root is nil then break
end

if i < n the construction impossible


### Checking without a tree construction

The basic idea is at each step to count how many nodes we can add to the tree. When we read $1$, we add one internal node which allows to add two new nodes and hence $-1+2 = 1$ and so we increment the counter by one. When we read $0$ we add a new leaf and so we decrement the counter.

if a[0] == 0 then
return FAILURE
else
counter = 2

for i=2 to n
if a[i] == 1 then
counter = counter + 1
else
counter = counter - 1
end

if counter == 0 then break
end

if i < n then
return FAILURE
else
return SUCCESS
end


### Construction example

$1,1,0,1,1,0,0,1$

  1 =>  1  => 1  => ... =>  1
/     /             /
1     1             1
/ \           / \
0   1         0   1
/ \
1   1
/ \
0   0


### Checking example

c=2, c=3, c=2,c=3, c=4, c=3, c=2, c=3, SUCCESS

At the end c=3 means we still can add 3 leaves.

• Your first algorithm initiates a tree reconstruction, assuming that any non-leaf node has a left child node. How do you prove that if no binry tree can be reconstructed from the sequence under your rule, then under no other rules can we reconstruct a tree. – Harold H. Oct 24 '17 at 11:04
• I have doubts for this part: "In the case 1, 1, ..., a_n we create a ROOT and we have a subsequence ... ". Even if the original sequence is reconstructable, the suffix "1, ..., a_n" may not be reconstructable. Ex. 1, 1, 0, 0, 1, 1 is reconstructible but 1, 0, 0, 1, 1 isn't. – Harold H. Oct 24 '17 at 12:19
• @HaroldH. By the induction $1\dots a_n$ is reconstructible. – fade2black Oct 24 '17 at 12:21
• No. You only prove that if $1, a_2, ..., a_n$ is reconstructible for all $n \le N$, then $1, 0, 1, ..., a_{N-1}$ and $1, 1, a_2, ..., a_{N}$ are reconstructible. To correctly use the induction (since your purpose is to prove $1, a_2, ..., a_n$ for any $n$ is reconstructible), you also have to prove sequences of the form $1, 0, 0, a_1, ..., a_{N-2}$ is reconstrutible. In fact it is not. – Harold H. Oct 24 '17 at 12:56
• @HaroldH. Such sequence is not reconstrutible. One of the second of third symbols must be 1. Otherwise there is no tree producing such sequence. I mention this case in my proof. What I prove that if such tree exists then the algorithm does reconstructs. – fade2black Oct 24 '17 at 13:01

The idea of construction in fade2black's answer is correct (while the pseudocode may be buggy). I rewrite it here:

FOR i = 2 to n:
IF root.left is free:
root.left = make_node(n[i])
IF n[i] == 1:
root = root.left
ELSE:
# backtrack until root.right is free or we reach the ROOT - highest node
WHILE root is not nil AND root.right is not free:
root = root.parent
IF root is nil:
RETURN failure
root.right = make_node(n[i])
IF n[i] == 1:
root = root.right


Its correctness can be proved by mathematical induction on $$n$$. Base cases are trivial.

Assume a sequence of length less than $$n$$ is valid if and only if a tree can be constructed by the algorithm. Now consider a sequence of length $$n$$.

If a tree can be constructed by the algorithm, the sequence is obviously valid.

On the other hand, if the sequence is valid, it must be $$1, a_1,\ldots,a_p, b_1,\ldots,b_q$$ where $$a_1,\ldots, a_p$$ and $$b_1,\ldots,b_q$$ are both valid sequences ($$p$$ or $$q$$ may be 0). By inductive assumption, the algorithm can construct a tree as the left subtree of the root from $$a_1,\ldots,a_p$$. Then the algorithm is handling $$b_1$$. Note the right child of the root is free, so the algorithm will not return "failure" during backtracking and successfully constructs $$b_1$$. By inductive assumption again, the algorithm sequentially constructs a subtree from $$b_1,\ldots,b_q$$. As a result, a tree is successfully constructed from the sequence $$1,a_1,\ldots,a_p,b_1,\ldots,b_q$$.