Trees (based on pointers)
Binary trees: analysis
Tree1. An address P_{1} of a record of TNode type is given. The record consists of the Data field (of integer type) and the Left and Right fields (of PNode type). The given record (the root node) is linked by its Left and Right fields with records of the same type (named the left and right child nodes respectively). Output the Data fields of the tree root and its left and right children. Also output the addresses of left and right child nodes.
Tree2°. An address P_{1} of a record of TNode type (a tree root) is given. This record is linked by its Left and Right fields with records of the same type (child nodes); they, in turn, are linked with their own child nodes and so on, until records whose Left and Right fields are equal to nil. Some of the nodes may have one field (Left or Right) equals nil. Output the amount of tree nodes.
Tree3. A pointer P_{1} to the root of a nonempty tree and an integer K are given. Output the amount of nodes whose value equals K.
Tree4. A pointer P_{1} to the root of a nonempty tree is given. Output the sum of values of all tree nodes.
Tree5. A pointer P_{1} to the root of a nonempty tree is given. Output the amount of left child nodes (the tree root should not be counted).
Tree6°. A pointer P_{1} to the root of a nonempty tree is given. Nodes without children are called the external nodes or the leaf nodes (the leaves). Output the amount of leaf nodes.
Tree7. A pointer P_{1} to the root of a nonempty tree is given. Output the sum of values of all tree leaves.
Tree8. A pointer P_{1} to the root of a tree is given, the tree contains at least two nodes. Output the amount of tree leaves that are the right child nodes.
Tree9°. A pointer P_{1} to the root of a nonempty tree is given. The root node is said to be on the zero level, its child nodes — on the first level, and so on. Output the depth of the tree (that is, the maximal level of tree nodes). For example, the depth of a tree containing only a root node is equal to 0.
Tree10. A pointer P_{1} to the root of a nonempty tree is given. For each tree level (including the zero one) output the amount of its nodes. The tree depth is assumed to be not greater than 10.
Tree11. A pointer P_{1} to the root of a nonempty tree is given. For each tree level (including the zero one) output the sum of values of its nodes. The tree depth is assumed to be not greater than 10.
Tree12°. A pointer P_{1} to the root of a nonempty tree is given. Using the recursive algorithm named inorder tree walk output the values of all tree nodes as follows: output the left subtree (using inorder tree walk), then output the root node, then output the right subtree (using inorder tree walk too).
Tree13°. A pointer P_{1} to the root of a nonempty tree is given. Using the recursive algorithm named preorder tree walk output the values of all tree nodes as follows: output the root node, then output the left subtree (using preorder tree walk), then output the right subtree (using preorder tree walk too).
Tree14. A pointer P_{1} to the root of a nonempty tree is given. Using the recursive algorithm named postorder tree walk output the values of all tree nodes as follows: output the left subtree (using postorder tree walk), then output the right subtree (using postorder tree walk too), then output the root node.
Tree15. A pointer P_{1} to the root of a nonempty tree and an integer N (> 0) are given. The value of N is not greater than the amount of tree nodes. Output the values of tree nodes whose order numbers are not greater than N (the tree nodes are numbered from 1 using inorder tree walk — see Tree12).
Tree16. A pointer P_{1} to the root of a nonempty tree and an integer N (> 0) are given. The value of N is not greater than the amount of tree nodes. Output the values of tree nodes whose order numbers are N or greater (the tree nodes are numbered from 1 using postorder tree walk — see Tree14).
Tree17. A pointer P_{1} to the root of a nonempty tree and two integers N_{1}, N_{2} (0 < N_{1} < N_{2}) are given. The value of N_{2} is not greater than the amount of tree nodes. Output the values of tree nodes whose order numbers are in the range N_{1} to N_{2} (the tree nodes are numbered from 1 using preorder tree walk — see Tree13).
Tree18. A pointer P_{1} to the root of a nonempty tree and an integer L (≥ 0) are given. Using tree walk of any type (see Tree12−Tree14) output values of all nodes of the level L. Also output the amount N of these nodes. If the given tree does not contain nodes of level L then output 0.
Tree19. A pointer P_{1} to the root of a nonempty tree is given. Output the maximal value of the tree nodes and the amount of nodes with this value.
Tree20. A pointer P_{1} to the root of a nonempty tree is given. Output the minimal value of the tree nodes and the amount of leaves with this value (the amount may be equal to 0).
Tree21. A pointer P_{1} to the root of a nonempty tree is given. Output the minimal value of its leaves.
Tree22. A pointer P_{1} to the root of a tree is given, the tree contains at least two nodes. Output the maximal value of its internal nodes (that is, nodes with children).
Tree23. A pointer P_{1} to the root of a nonempty tree is given. Using preorder tree walk find the first tree node with the minimal value and output its address P_{2}.
Tree24. A pointer P_{1} to the root of a nonempty tree is given. Using inorder tree walk find the last node with the maximal odd value and output its address P_{2}. If the tree does not contain nodes with odd values then output nil.
Binary trees: creation
Tree25. An integer N (> 0) and a sequence of N integers are given. Create a tree with N nodes and assign values of the given sequence to tree nodes in order of their creation. Each node of the tree (except for the root) should be a right child. Output the address of the tree root.
Tree26. An integer N (> 0) and a sequence of N integers are given. Create a tree with N nodes and assign values of the given sequence to tree nodes in order of their creation. Each internal node of the tree should have one child: the root has a left child, which has a right child, which has a left child, and so on. Output the address of the tree root.
Tree27. An integer N (> 0) and a sequence of N integers are given. Create a tree with N nodes and assign values of the given sequence to tree nodes in order of their creation. Each internal node of the tree should have one child: an internal node whose value is an odd number has a left child, otherwise it has a right child. Output the address of the tree root.
Tree28. An even integer N (> 0) and a sequence of N integers are given. Create a tree with N nodes; left child nodes of the tree should be leaves, right child nodes should be internal ones. For each internal node create a left child at first, then create a right one (if it exists). Assign values of the given sequence to tree nodes in order of their creation. Output the address of the tree root.
Tree29. An even integer N (> 0) and a sequence of N integers are given. Create a tree with N nodes. Inner node whose value is an odd number should have a left child leaf, otherwise it should have a right child leaf. For each internal node create a child leaf node at first, and then create a child internal node (if it exists). Assign values of the given sequence to tree nodes in order of their creation. Output the address of the tree root.
Tree30. An integer N (> 0). Create a tree that satisfies the following conditions: the value of root node equals N; if the value of a node is an even number K then this node has only a left child whose value equals K/2; if the value of a node equals 1 then this node is a leaf; if the value of a node is another odd number K then this node has a left child whose value equals K/2 and has a right child whose value equals K − K/2 ("/" denotes the operator of integer division). Output the address of the tree root.
Tree31. Two positive integers L, N (N > L) and a sequence of N integers are given. Create a tree of depth L. Use elements of the given sequence as node values; add new nodes using the following algorithm: for each node of the level not greater than L create the node itself, then its left subtree of corresponding depth, and finally its right subtree. If less than N nodes are required to create an Ldepth tree then do not use the rest of elements of the given sequence. Output the address of the tree root.
Tree32°. An integer N (> 0) and a sequence of N integers are given. Create a balanced tree with N nodes (that is, a binary tree which satisfies the following condition: for each tree node the depth of its left subtree differs at most on 1 from the depth of its right subtree) and output the address of the tree root. Use elements of the given sequence as node values; create the tree by means of the following recursive algorithm: create a root node, then repeat the algorithm twice: for creating the left subtree with N/2 nodes and for creating the right subtree with N − 1 − N/2 nodes ("/" denotes the operator of integer division).
Tree33. An integer N (> 0) is given. Create a balanced tree with N nodes and output the address of the tree root. The value of each node should be equal to its level (for example, the root value is 0, the value of its children is 1, and so on). Create the balanced tree be means of the recursive algorithm described in Tree32.
Tree34°. An address P_{1} of the root of a nonempty tree is given. Create a copy of the tree and output the address P_{2} of its root.
Binary trees: changing
Tree35. A pointer P_{1} to the root of a nonempty tree is given. Double the value of each tree node.
Tree36. A pointer P_{1} to the root of a nonempty tree is given. Halve the value of each tree node whose initial value is an even number.
Tree37. A pointer P_{1} to the root of a nonempty tree is given. Add 1 to the value of each tree leaf and subtract 1 from the value of each internal node.
Tree38. A pointer P_{1} to the root of a nonempty tree is given. For each tree node with two child swap values of its child nodes (that is, swap values of Data fields of child nodes).
Tree39. A pointer P_{1} to the root of a nonempty tree is given. Swap child nodes of each internal node in the tree (that is, swap values of its Left and Right field).
Tree40°. A pointer P_{1} to the root of a nonempty tree is given. Remove all nodes from the tree (except the root), release the memory allocated for removed nodes, and assign nil to the Left and Right fields of the root.
Tree41. A pointer P_{1} to the root of a nonempty tree is given, the tree contains at least two nodes. Remove all tree leaves and assign nil to the Left and Right fields of their parents. Release the memory allocated for removed nodes.
Tree42. A pointer P_{1} to the root of a nonempty tree is given. Remove all nodes whose value is less than the root value, together with all their descendants. Release the memory allocated for removed nodes.
Tree43. A pointer P_{1} to the root of a nonempty tree is given. Apply the following action to each tree node that has two child nodes: if the node value is an even number then remove its right child, otherwise remove its left child. Use preorder tree walk; each node should be removed together with all its descendants. Release the memory allocated for removed nodes.
Tree44. A pointer P_{1} to the root of a nonempty tree is given. Add two child nodes to each tree leaf; the values of left and right child nodes should be equal to 10 and 11 respectively.
Tree45. A pointer P_{1} to the root of a nonempty tree is given. Add one child node to each thee leaf; if the leaf value is an odd number then its child should be a left node, otherwise its child should be a right one. Value of created child node should be equal to value of its parent.
Tree46. A pointer P_{1} to the root of a nonempty tree is given. For each tree node with one child add another child node (a leaf). Value of created child node should be equal to doubled value of its parent.
Tree47°. A pointer P_{1} to the root of a nonempty tree is given. Transform the given tree to a perfect tree by adding some new nodes (a perfect tree is a binary tree whose all leaves are at the same level). Do not change the initial depth of the tree; value of all new nodes should be equal to −1.
Doubly linked binary trees
Tree48. An address P_{1} of a tree node is given. Tree node is a record of TNode type containing the Data field (of integer type) and the Left, Right, and Parent fields (of PNode type). The Left and Right fields point to the left and right child nodes respectively, the Parent field points to the parent node (the Parent field of the root node equals nil). Output pointers P_{L}, P_{R} to the left and right child of the given node, P_{0} to the its parent, and P_{2} to its sibling (siblings are nodes that have the same parent). If some of required nodes are not exist then output nil for each absent node.
Tree49°. A pointer P_{1} to the root of a tree is given. Tree nodes are represented by records of TNode type; they are linked by the Left and Right fields of TNode record. Using the Parent field of TNode record transform the given tree into a doubly linked tree whose each node is connected not only with its child nodes (by the Left and Right fields) but also with its parent node (by the Parent field). The Parent field of the root node should be equal to nil.
Tree50. A pointer P_{1} to some node of a doubly linked tree is given. Output the pointer P_{2} to the tree root.
Tree51. Pointers P_{1}, P_{2}, P_{3} to three nodes of a doubly linked tree are given. Output the level of each node (the level of the root equals 0).
Tree52. Pointers P_{1} and P_{2} to two different nodes of a doubly linked tree are given. Output the degree of relationship of the node P_{1} to the node P_{2} (the degree of relationship equals −1 if the node P_{2} is not in the chain of ancestors of the node P_{1}; otherwise it equals L_{1} − L_{2}, where L_{1} and L_{2} are the levels of nodes P_{1} and P_{2} respectively).
Tree53°. Pointers P_{1} and P_{2} to two different nodes of a doubly linked tree are given. Find the nearest mutual ancestor of the nodes P_{1} and P_{2} and output its pointer P_{0}.
Tree54. A pointer P_{1} to the node of a doubly linked tree is given. Create a copy of the given tree and output a pointer P_{2} to the root of the created tree.
Tree55. A pointer P_{1} to the nonroot node of a doubly linked tree is given. If the node P_{1} has a sibling then remove the sibling together with all its descendants from the tree and release the memory allocated for removed nodes, if the node P_{1} has no sibling then create it and all its descendants as a copy of the subtree with the root P_{1}. Output the pointer P_{0} to the parent of P_{1}.
Tree56. Two positive integers L, N (N > L) and a sequence of N integers are given. Create a doubly linked tree of depth L. Use elements of the given sequence as node values; add new nodes using the following algorithm: for each node of the level not greater than L create the node itself, then its left subtree of corresponding depth, and finally its right subtree. If less than N nodes are required to create an L depth tree then do not use the rest of elements of the given sequence. Output the address of the tree root.
Binary search trees
Tree57. A pointer P_{1} to the root of a nonempty tree is given. It the tree is a search tree, that is, values of its nodes form a nondecreasing sequence in inorder tree walk, then output nil; otherwise output the address of the first node (in inorder tree walk) that breaks the searchtree property.
Tree58. A pointer P_{1} to the root of a nonempty tree is given. It the tree is a nonrecurrent search tree, that is, values of its nodes form an increasing sequence in inorder tree walk, then output nil; otherwise output the address of the first node (in inorder tree walk) that breaks the searchtree property.
Tree59°. A pointer P_{1} to the root of a nonempty nonrecurrent search tree and an integer K are given. If the tree contains a node whose value equals K then output the address P_{2} of this node, otherwise output nil. Also output the amount N of tree nodes that were checked during the search.
Tree60. A pointer P_{1} to the root of a nonempty search tree and an integer K are given. Output the amount C of tree nodes whose value equals K. Also output the amount N of tree nodes that were checked during the search.
Tree61. A pointer P_{1} to the root of a search tree and an integer K are given (if the tree is empty then P_{1} = nil). Add a new node with the value K to the tree so that the tree still remains a search tree. Output the pointer P_{2} to the root of the resulting tree. Use the following recursive algorithm for a tree with the root P: if P = nil then create a leaf with the value K and assign the address of the leaf to the pointer P; if the tree root exists then repeat the algorithm for the left subtree in case K is less than the root value or for the right subtree otherwise.
Tree62. A pointer P_{1} to the root of a nonrecurrent search tree and an integer K are given (if the tree is empty then P_{1} = nil). Add a new node with the value K to the tree so that the tree still remains a nonrecurrent search tree. Do not change the given tree if it already contains a node with the value K. Output the pointer P_{2} to the root of the resulting tree. Use the following recursive algorithm for a tree with the root P: if P = nil then create a leaf with the value K and assign the address of the leaf to the pointer P; if the tree root exists then repeat the algorithm for the left subtree in case K is less than the root value or for the right subtree in case K is greater than the root value.
Tree63. An integer N (> 0), a sequence of N integers and a pointer P_{1} to the root of a search tree are given (if the tree is empty then P_{1} = nil). Add N new nodes with values from the given sequence to the tree so that the tree still remains a search tree. Output the pointer P_{2} to the root of the resulting tree. Use the recursive algorithm described in Tree61 to add each new node.
Tree64. An integer N (> 0), a sequence of N integers and a pointer P_{1} to the root of a nonrecurrent search tree are given (if the tree is empty then P_{1} = nil). Add N new nodes with values from the given sequence to the tree so that the tree still remains a nonrecurrent search tree. Output the pointer P_{2} to the root of the resulting tree. Use the recursive algorithm described in Tree62 to add each new node.
Tree65°. An integer N (> 0) and a sequence of N integers are given. Sort the sequence by creating a search tree (use the recursive algorithm described in Tree61 to add each new node). Output the pointer P_{1} to the root of the created tree. Also output elements of the sorted sequence using the inorder tree walk.
Tree66. An integer N (> 0) and a sequence of N integers are given. Sort all different elements of the sequence by creating a nonrecurrent search tree (use the recursive algorithm described in Tree62 to add each new node). Output the pointer P_{1} to the root of the created tree. Also output elements of the sorted sequence using the inorder tree walk.
Tree67. Two pointers are given: P_{1} to the root of a nonempty search tree and P_{2} to one of its nodes with no more than one child. Remove the node P_{2} from the tree so that the tree still remains a search tree (if the node P_{2} has a child then link the child with the parent of the node P_{2}). If the resulting tree is not empty then output the pointer P_{3} to its root, otherwise output nil.
Tree68. Two pointers are given: P_{1} to the root of a nonempty search tree and P_{2} to one of its nodes with two children. Remove the node P_{2} from the tree so that the tree still remains a search tree. Use the following algorithm: find the node P with the maximal value in the left subtree of the node P_{2}, then assign its value to the node P_{2}, and finally remove the node P as in Tree67 (because the node P should have no more than one child).
Tree69. Two pointers are given: P_{1} to the root of a nonempty search tree and P_{2} to one of its nodes with two children. Remove the node P_{2} from the tree so that the tree still remains a search tree. Use the following algorithm: find the node P with the minimal value in the right subtree of the node P_{2}, then assign its value to the node P_{2}, and finally remove the node P as in Tree67 (because the node P should have no more than one child).
Tree70°. A pointer P_{1} to a node of a doubly linked search tree is given. Remove the node P_{1} from the tree so that the tree still remains a doubly linked search tree. If the resulting tree is not empty then output the pointer P_{2} to its root, otherwise output nil. If the node P_{1} has two children then use the algorithm described in Tree68 for its removing.
Tree71. A pointer P_{1} to a node of a doubly linked search tree is given. Remove the node P_{1} from the tree so that the tree still remains a doubly linked search tree. If the resulting tree is not empty then output the pointer P_{2} to its root, otherwise output nil. If the node P_{1} has two children then use the algorithm described in Tree69 for its removing.
Binary parse trees
Tree72. A string S that represents a nonempty tree is given. The tree representation is defined as follows (blank characters are not used): <tree>  ::=  <empty string>     <node>(<left subtree>,<right subtree>)  <node>  ::=  <digit> 
For example, "4(2(,),6(,7(3(,),)))". Create a tree represented by the string S and output the pointer to its root.
Tree73. A pointer P_{1} to the root of a nonempty tree is given. Output the string that describes the tree using the representation specified in Tree72.
Tree74°. A string S that represents a nonempty tree is given. The tree representation is defined as follows (blank characters are not used, the node representation depends on presence of subtrees of the node): <tree>  ::=  <node>     <node>(<left subtree>,<right subtree>)     <node>(<left subtree>)     <node>(,<right subtree>)  <node>  ::=  <digit> 
For example, "4(2,6(,7(3)))". Create a tree represented by the string S and output the pointer to its root.
Tree75°. A pointer P_{1} to the root of a nonempty tree is given. Output the string that describes the tree using the representation specified in Tree74.
Tree76°. A string S that represents a correct expression of integer type is given. The expression is defined as follows (blank characters are not used): <expression>  ::=  <digit>     (<expression><operator><expression>)  <operator>  ::=  +  −  * 
Create a tree that represents the given expression (a parse tree): each internal node corresponds to one of the arithmetic operators and equals −1 for addition, −2 for subtraction, and −3 for multiplication; a left subtree of a nodeoperator represents its left operand and a right subtree represents its right operand; leaf nodes represent digits. Output the pointer to the root of the created tree.
Tree77. A string S that represents a correct expression of integer type is given. The expression is defined as follows (the parenthesisfree preorder format): <expression>  ::=  <digit>     <operator> <expression> <expression>  <operator>  ::=  +  −  * 
Expressions are separated from each other and from the operators by one blank character. Create a parse tree for the given expression and output the pointer to its root. See the description of parse tree structure in Tree76; a left subtree of the nodeoperator corresponds to its first operand and a right subtree corresponds to its second operand.
Tree78. A string S that represents a correct expression of integer type is given. The expression is defined as follows (the parenthesisfree postorder format): <expression>  ::=  <digit>     <expression> <expression> <operator>  <operator>  ::=  +  −  * 
Expressions are separated from each other and from the operators by one blank character. Create a parse tree for the given expression and output the pointer to its root. See the description of parse tree structure in Tree76; a left subtree of the nodeoperator corresponds to its first operand and a right subtree corresponds to its second operand.
Tree79°. A pointer P_{1} to the root of a nonempty parse tree is given (see the description of parse tree structure in Tree76). Output the value of expression that corresponds to the given tree.
Tree80. A pointer P_{1} to the root of a nonempty parse tree is given (see the description of parse tree structure in Tree76). Output the string representation of expression that corresponds to the given tree. Use the expression format specified in the same task: <expression>  ::=  <digit>     (<expression><operator><expression>)  <operator>  ::=  +  −  * 
Tree81. A pointer P_{1} to the root of a nonempty parse tree is given. Output the string representation of expression that corresponds to the given tree. Use the parenthesisfree preorder format (see Tree77).
Tree82. A pointer P_{1} to the root of a nonempty parse tree is given. Output the string representation of expression that corresponds to the given tree. Use the parenthesisfree postorder format (see Tree78).
Tree83. A string S that represents a correct expression of integer type is given. The expression is defined as follows (blank characters are not used, functions M and m return their maximal and minimal argument respectively): <expression>  ::=  <digit>  M(<expression> , <expression>)     m(<expression> , <expression>) 
Create a parse tree for the given expression: each internal node corresponds to one of two available functions and equals −1 for the function M and −2 for the function m; a left subtree of a nodefunction represents its first argument and a right subtree represents its second argument; leaf nodes represent digits. Output the pointer to the root of the created tree.
Tree84. A pointer P_{1} to the root of a nonempty parse tree is given (see the description of parse tree structure in Tree83). Output the value of expression that corresponds to the given tree.
Tree85. A pointer P_{1} to the root of a nonempty parse tree is given (see the description of parse tree structure in Tree83). Output the string representation of expression that corresponds to the given tree. Use the expression format specified in the same task: <expression>  ::=  <digit>  M(<expression> , <expression>)     m(<expression> , <expression>) 
General trees
Tree86°. In a general tree a node may have more than two child nodes arranged in fixed order (from left to right). A general tree may be represented by linked records of the TNode type as follows: the Left field of any node points to its leftmost child whereas the Right field points to the nearest right sibling of this node. The tree root has no siblings, therefore its Right field always equals nil. A pointer P_{1} to the root of a nonempty binary tree is given. Create a general tree that corresponds to the given binary tree and output the pointer P_{2} to the root of the created general tree.
Tree87. A pointer P_{1} to the root of a nonempty general tree is given. Each node has no more than two child nodes. Create a binary tree corresponding to the given general tree and output the pointer P_{2} to the root of the created binary tree. First child of any node of general tree should be the left child of the correspondent node of binary tree.
Tree88. A pointer P_{1} to the root of a nonempty general tree is given. Output the depth of the tree (that is, the maximal level of tree nodes). All siblings are assumed to be on the same level; the level of the root equals 0.
Tree89. A pointer P_{1} to the root of a nonempty general tree is given. For each tree level (including the zero one) output the amount of its nodes. The tree depth is assumed to be not greater than 10.
Tree90. A pointer P_{1} to the root of a nonempty general tree is given. For each tree level (including the zero one) output the sum of values of its nodes. The tree depth is assumed to be not greater than 10.
Tree91. A pointer P_{1} to the root of a nonempty general tree and an integer L (≥ 0) are given. Output the values of nodes of the level L and their amount N (nodes must be ordered from left to right). If nodes of the level L are absent then output 0.
Tree92°. A pointer P_{1} to the root of a nonempty general tree is given. Output the values of all nodes using inorder tree walk as follows: output the first (i. e., the most left) subtree using inorder tree walk, then output the root value, then output all other subtrees (from left to right) using inorder tree walk too.
Tree93. A pointer P_{1} to the root of a nonempty general tree is given. Output the values of all nodes using postorder tree walk as follows: output all subtrees (from left to right) using postorder tree walk, then output the root value.
Tree94. A pointer P_{1} to the root of a nonempty general tree and an integer N (≥ 0) are given. Output the amount of nodes that have exactly N child nodes (this amount may be equal to 0).
Tree95. A pointer P_{1} to the root of a nonempty general tree is given. Output the pointer P_{2} to the first node that has the maximal amount of child nodes. Use inorder tree walk (see Tree92).
Tree96. A pointer P_{1} to the root of a nonempty general tree is given. Output the pointer P_{2} to the last node that has the maximal sum of values of child nodes. Use postorder tree walk (see Tree93).
Tree97. A pointer P_{1} to the root of a nonempty general tree is given. In each set of siblings find the maximal value (that is, the maximal Data field) and assign this value to each node of the set.
Tree98. A pointer P_{1} to the root of a nonempty general tree is given. In each set of siblings inverse the order of the node values (that is, swap the Data fields of the first and the last sibling, then swap the Data fields of the second and the last but one sibling, and so on).
Tree99. A string S that represents a nonempty general tree is given. The tree representation is defined as follows (blank characters are not used, siblings are ordered from left to right): <tree>  ::=  <node>     <node>(<list of subtrees>)  <list of subtrees>  ::=  <tree>     <tree>,<list of subtrees>  <node>  ::=  <digit> 
For example, "3(2,7(6,4,5),8(4(2,3),5(1)))". Create a tree represented by the string S and output the pointer to its root.
Tree100. A pointer P_{1} to the root of a nonempty general tree is given. Output the string that describes the tree using the representation specified in Tree99.
