6
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Harold H. Oct 24 '17 at 11:04
  • $\begingroup$ 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. $\endgroup$ – Harold H. Oct 24 '17 at 12:19
  • $\begingroup$ @HaroldH. By the induction $1\dots a_n$ is reconstructible. $\endgroup$ – fade2black Oct 24 '17 at 12:21
  • $\begingroup$ 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. $\endgroup$ – Harold H. Oct 24 '17 at 12:56
  • $\begingroup$ @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. $\endgroup$ – fade2black Oct 24 '17 at 13:01
0
$\begingroup$

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

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