Statistics

Problem Statement for "SymmetricalTree"

Problem Statement

Consider the following code, which traverses a tree and prints a sequence of characters: 

    bypass(Node v) {
        for i=0..size(v.children)-1 {
            write('1');
            bypass(v.children[i]);
            write('0');
        }
    }

Starting from the root this code will generate a string of 0's and 1's that fully describes a tree. For example, "1101100110011000" will represent the tree in the following picture (nodes are marked in the order of traversal).

A tree is called symmetrical if, after reversing the order of children for all nodes, the string representation of the tree is not changed. For example, the tree in the picture is not symmetrical because the string representation changes to "1110011001100100" after the order of children is reversed for all nodes.

You will be given a String tree. You are to make it symmetrical by removing some nodes and changing the order of children for some nodes. You can remove a node only if all its children are removed too. You should return tree after making it symmetrical. If there are multiple ways to make tree symmetrical, you should minimize the number of removed nodes. If two or more solutions still remain, return the one that comes first lexicographically.

Definition

Class:
SymmetricalTree
Method:
makeSymmetrical
Parameters:
String
Returns:
String
Method signature:
String makeSymmetrical(String tree)
(be sure your method is public)

Constraints

  • tree will contain between 1 and 40 characters, inclusive.
  • tree will only contain the digits '0' and '1'.
  • tree will represent a valid tree.

Examples

  1. "1101100110011000"

    Returns: "11011001100100"

    This is the example from the problem statement. We should remove the 9th node (see picture).

  2. "10101100"

    Returns: "10110010"

    We can make the tree symmetrical by using only rearrangements.

  3. "1011100100"

    Returns: "110100"

  4. "101101100110101000"

    Returns: "11011010100100"

  5. "11010010110110010101100010110100"

    Returns: "10110100110110010110010011010010"

  6. "101110011000101100"

    Returns: "10111001100010"

  7. "11101001011010100101010011010100"

    Returns: "1101011010011010010100"

  8. "1110101110001011000100"

    Returns: "111010111000101000"

  9. "101101010101001010"

    Returns: "1011010101010010"

  10. "101011001011101001010100"

    Returns: "10101101101001001010"

  11. "1110001011001101011100010100"

    Returns: "110011010111000101001100"

  12. "1101001011010101010100"

    Returns: "101101010101010010"

  13. "1010110101110100101010111000110000"

    Returns: "101101101100110100110010010010"

  14. "110101011001100100"

    Returns: "110101100110010100"

  15. "10101101101011000100"

    Returns: "10110110110010010010"

  16. "10"

    Returns: "10"

  17. "101101011001010010"

    Returns: "101101011001010010"

  18. "10101010110010110101101000"

    Returns: "101010110110100100101010"

  19. "1111001010101100011010011000"

    Returns: "11100110110010110010011000"

  20. "101101010110010101101001101000"

    Returns: "11010101101001101001010100"

  21. "11001011010011001101011000"

    Returns: "1011001101100100110010"

  22. "110101100110100100"

    Returns: "1101011010010100"

  23. "1100"

    Returns: "1100"

  24. "10111010010100"

    Returns: "110110100100"

  25. "10101010101011001010111010110101001000"

    Returns: "10101010111011010100100010101010"

  26. "10101011100010101010110100"

    Returns: "1010101011010010101010"

  27. "1111000101010101101011101001010000"

    Returns: "1101011011011010010010010100"

  28. "1010110100101011100110100010"

    Returns: "1010101110011000101010"

  29. "1011001110110010101000"

    Returns: "10111010110010100010"

  30. "10101101100011001011100111010000"

    Returns: "101011011000111001001010"

  31. "101010101010111110000010111100001100"

    Returns: "10101010111100001111000010101010"

  32. "111010010101101001100011001100"

    Returns: "110011011010011001101001001100"

  33. "10101011001110010101001010111000"

    Returns: "10101100110101010011001010"

  34. "10110010110110100101001100110100"

    Returns: "101100110100110100110010"

  35. "11100010110010110101110000"

    Returns: "101100110111000100110010"

  36. "1010110101101001100101011000"

    Returns: "1011010110011010011001010010"

  37. "101110100010101111001101001101001000"

    Returns: "1010111011010011010010001010"

  38. "10110010110111100001010101010101010100"

    Returns: "1011010101010111100001010101010010"

  39. "11101010011100100010101110100100"

    Returns: "101101101000111010010010"

  40. "10111011001010110110101010010001100100"

    Returns: "11011010110110101010010010100100"

  41. "1101010101001110010100110010110100"

    Returns: "1011010011010101010011010010"

  42. "10101101100010101101011010101000"

    Returns: "101011011000111001001010"

  43. "1100111110001010010100"

    Returns: "110110111000100100"

  44. "11101010010011010110100101011000"

    Returns: "11011010001110100100"

  45. "10101011100101001100"

    Returns: "101011011001001010"

  46. "11110010100101111001000110100101011000"

    Returns: "110101101001110100011010010100"

  47. "11001011001101101001100110110110001000"

    Returns: "110011100110110100100110001100"

  48. "1011001100110110100101011001001101011000"

    Returns: "101100110101100110010100110010"

  49. "10110011010110011001011000101010111000"

    Returns: "1010110011010110011001010011001010"

  50. "110100101100110101010110001110100100"

    Returns: "101101001101011001010011010010"

  51. "11011010011001010101010110011100101000"

    Returns: "1101010110011010011010011001010100"

  52. "1010101010110101001100111000101011011000"

    Returns: "101010101110001101010011100010101010"

  53. "1100101011011001010111001010010101011000"

    Returns: "101101010110011011001001100101010010"

  54. "1110010010111100011100001101010101001100"

    Returns: "10110110001101010101001110010010"

  55. "1101010110001111011000011100110110001000"

    Returns: "1111011000011110010000"

  56. "101101001011101001010111100010010100"

    Returns: "10110101101001101001010010"

  57. "1010101010110101010100101100110011110000"

    Returns: "10101011001101010101001100101010"

  58. "1101011100010110010100111001101011010000"

    Returns: "111001110000111100011000"

  59. "1100111010100101010100110101010111000100"

    Returns: "11010101011000110011100101010100"

  60. "10110010111001010110010111010110010000"

    Returns: "101101100111010101000110010010"

  61. "1100110011100111000101001011011000110100"

    Returns: "1100110100110110011001001101001100"

  62. "10110011011010100110010101010101010100"

    Returns: "1011010101010110101001010101010010"

  63. "11011011010010010110110010011001011000"

    Returns: "110110011010110001011100101001100100"

  64. "1010110010110011101001010110010101001100"

    Returns: "101011001101010110100101010011001010"

  65. "1011010101011010010100101011011010110000"

    Returns: "1010110101011010010101001010"

  66. "11001101001110010101110001101011000100"

    Returns: "11001101100110110010011001001100"

  67. "10"

    Returns: "10"

  68. "1100"

    Returns: "1100"

  69. "1010"

    Returns: "1010"

  70. "110010"

    Returns: "1010"

  71. "110100"

    Returns: "110100"

  72. "101100"

    Returns: "1010"

  73. "10110010"

    Returns: "10110010"

  74. "10111000"

    Returns: "111000"

  75. "10101100"

    Returns: "10110010"

  76. "1101011000"

    Returns: "1101100100"

  77. "11110000"

    Returns: "11110000"

  78. "1100101100"

    Returns: "1100101100"

  79. "10101100"

    Returns: "10110010"

  80. "11001010"

    Returns: "10110010"

  81. "1011100100"

    Returns: "110100"

  82. "11101000"

    Returns: "11101000"

  83. "1010101100"

    Returns: "10101010"

  84. "1010110100"

    Returns: "1011010010"

  85. "11011000"

    Returns: "110100"

  86. "1011100100"

    Returns: "110100"

  87. "10110100"

    Returns: "110100"

  88. "1010110100"

    Returns: "1011010010"

  89. "1010101010"

    Returns: "1010101010"

  90. "1010101010101010101010101010101010101010"

    Returns: "1010101010101010101010101010101010101010"

  91. "1101010101010101010101010101010101010100"

    Returns: "1101010101010101010101010101010101010100"

  92. "1111111111111111111100000000000000000000"

    Returns: "1111111111111111111100000000000000000000"

  93. "1111111111000000000011111111110000000000"

    Returns: "1111111111000000000011111111110000000000"

  94. "1100110011001100110011001100110011001100"

    Returns: "1100110011001100110011001100110011001100"

  95. "1101001101001101001101001101001101001010"

    Returns: "1011010011010011010011010011010011010010"

  96. "1101001101001101001101001101001101001100"

    Returns: "1101001101001101001100110100110100110100"

  97. "1110111011101110111011101100000000000000"

    Returns: "1111111111111010000000000000"

  98. "1111111111111111111010000000000000000000"

    Returns: "1111111111111111111010000000000000000000"

  99. "1111111111111111101000000000000000001100"

    Returns: "111111111111111110100000000000000000"

  100. "1111111111111111010000000000000000110010"

    Returns: "10111111111111111101000000000000000010"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: