TopCoder problem "MutateTree" used in TCCC07 Round 1B (Division I Level Two)



Problem Statement

    A 2-tree is a tree in which each vertex either has exactly 2 non-empty children (its left and right child), or is a leaf (has no children). Each leaf is named with an uppercase letter, and each other vertex is named with a lowercase letter.

We want to mutate a given 2-tree by swapping the locations of two of its subtrees. For example, below is shown a 2-tree and then its mutation when its subtrees rooted at C and x are swapped.

      q                      q
  x       z        ==>    C       z
 A B    C   g                   x    g
           R Q                 A B  R Q
Each 2-tree can be represented by a string consisting of the names of its vertices in the order given by a post-order traversal of the tree (see notes). Given tree, the representation of a 2-tree, and the 0-based indices of two of its vertices, return the representation of the mutated tree. If the two subtrees have any vertices in common return the 7-character string "OVERLAP". If tree is not the representation of any 2-tree, return "BADTREE".
 

Definition

    
Class:MutateTree
Method:newTree
Parameters:String, int, int
Returns:String
Method signature:String newTree(String tree, int root1, int root2)
(be sure your method is public)
    
 

Notes

-A post-order print of a 2-tree rooted at root is defined recursively as follows:
if root is not a leaf

    post-order print the left subtree

    post-order print the right subtree

print the root's letter.
 

Constraints

- tree will contain between 1 and 50 characters, inclusive.
- Each character in tree will be a letter ('A'-'Z','a'-'z').
- The characters in tree will be distinct.
- root1 and root2 will each be between 0 and n-1, inclusive, where n is the number of characters in tree.
 

Examples

0)
    
"ABxCRQgzq"
3
2
Returns: "CABxRQgzq"
This is the example above, in which the subtrees rooted at C and x are swapped.
1)
    
"rAB"
1
2
Returns: "BADTREE"
The post-order print of every (non-empty) 2-tree starts with a leaf.
2)
    
"ABxCRQgzq"
3
7
Returns: "OVERLAP"
This is the tree shown in the problem. The two indicated subtrees are the ones rooted at C and at z. They overlap since vertex C is in both of them.
3)
    
"CEGHfdbIa"
3
2
Returns: "CEHGfdbIa"
4)
    
"X"
0
0
Returns: "OVERLAP"
This tree is a legal 2-tree containing only one leaf. The subtrees are the entire tree -- they overlap.
5)
    
"IPDqWmSbEa"
9
1
Returns: "BADTREE"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7811

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10897&pm=7811

Writer:

dgoodman

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Recursion