Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that an ordered rooted tree is uniquely determined when a list of vertices generated by a preorder traversal of the tree and the number of children of each vertex are specified.

share|improve this question
    
What is the list of verticies generated by a preorder transversal ? –  Amr Nov 10 '12 at 12:40
    
@Amr sequence of preorder traversal from a tree. –  geni Nov 10 '12 at 12:43

2 Answers 2

up vote 2 down vote accepted

If the root of the tree has $k$ children, the root is followed in the preorder sequence by $k$ preorder sequences of the children, by definition. Unfortunately we do not know where these sequences start. That can be solved recursively. In the root start $k$ consecutive functions preorder-read (with root as starting point). At the start of each function it marks the next vertex $v$ from the preorder list as child of its starting point, and recusively starts as many copies of itself as the number of children indicated by the child-number of $v$, this time remembering $v$ as starting point.

(added) If you want an inductive argument, then take the following approach. The leftmost path in the tree, given the preorder is easily found: it consists if the first vertices $v_1, \dots v_k$ of the ordering ending by a leaf $v_k$ (which is marked as having 0 children). Now remove that leaf $v_k$ from the ordering, and also subtract 1 from the number of children of its predecessor $v_{k-1}$ (which is its father). The new sequence (by induction hypothesis) uniquely determines a tree. The initial tree is easily obtained from that tree by adding the removed leaf $v_k$ as first child to $v_{k-1}$.

share|improve this answer

I'm not good at formalizing proofs in graph theory. My hint is to try constructing an ordered, rooted tree given a preorder traversal and the number of children of each vertex. Going through the preorder traversal you start with the root (by definition of a preorder traversal). Then you perform a preorder traversal on each of of the subtrees rooted at its children, left to right. It's recursive by nature so an inductive argument seems to fall out (you could also do this by contradiction, but the direct proof is arguably more natural). In particular, prove by induction on the number of nodes that the claim holds. For $n = 1$ you only have one tree (well, you can have different vertex labels, but they're all the same tree)--of course it's unique! For the general case, you're given the number of children the root has. As we said before, the subtrees rooted at its children will be traversed left to right. Those subtrees are smaller, so by induction they are unique. The entire tree must also be unique (you must argue this).

Edit In retrospect, there is no requirement for preorder traversal to go over the children in any order... but that's not what we really want anyways. It just matters that the subtrees rooted at the children are traversed separately.

share|improve this answer
    
I don not know how to prove with induction in step K+1? (you said subtrees traversed left to right then subtrees are smaller but how to prove that they are unique?)how to i should remove end leaf and apply to inductive hypothesis? –  geni Nov 10 '12 at 13:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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