Programming Taskbook

1100 training tasks on programming

Main

Tasks

Examples

PT for MPI-2

Overview

Input-output operations

Task groups

Tree

Tasks | Task groups | Tree

Trees (based on pointers)

All numbers mentioned in the tasks of this group are of integer type. All pointers are of PNode type; they point to records of TNode type. In the tasks of this group the Data, Left, Right, and Parent fields of the TNode record are used, therefore one can assume that the PNode and TNode types are defined as follows:

[Pascal]

type
PNode = ^TNode;
TNode = record
Data: integer;
Left: PNode;
Right: PNode;
Parent: PNode;
end;

[C/C++]

struct Node; typedef struct Node TNode; typedef struct Node *PNode; struct Node
{
int Data;
PNode Left;
PNode Right;
PNode Parent;
};

In the most of the tasks only the Data, Left, and Right fields of the TNode record are used. The Parent field is required in the tasks devoted to doubly linked trees.

The value of the Data field of a variable of TNode type is considered as the value of the corresponding tree node.

In C/C++ programs, the DeleteNode(p) function call (or, in C++, the delete p operator) should be used to free the memory that a pointer p (of the PNode type) addresses.

The following formulations are oriented to the Pascal language; the C/C++ version uses NULL as the null pointer name.

Binary trees: analysis

Tree1. An address P₁ 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₁ 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₁ 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₁ to the root of a nonempty tree is given. Output the sum of values of all tree nodes.

Tree5. A pointer P₁ 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₁ 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₁ to the root of a nonempty tree is given. Output the sum of values of all tree leaves.

Tree8. A pointer P₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ to the root of a nonempty tree and two integers N₁, N₂ (0 < N₁ < N₂) 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 in the range N₁ to N₂ (the tree nodes are numbered from 1 using preorder tree walk — see Tree13).

Tree18. A pointer P₁ 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₁ 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₁ 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₁ to the root of a nonempty tree is given. Output the minimal value of its leaves.

Tree22. A pointer P₁ 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₁ 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₂.

Tree24. A pointer P₁ 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₂. 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 L-depth 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₁ of the root of a nonempty tree is given. Create a copy of the tree and output the address P₂ of its root.

Binary trees: changing

Tree35. A pointer P₁ to the root of a nonempty tree is given. Double the value of each tree node.

Tree36. A pointer P₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₀ to the its parent, and P₂ 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₁ 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₁ to some node of a doubly linked tree is given. Output the pointer P₂ to the tree root.

Tree51. Pointers P₁, P₂, P₃ 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₁ and P₂ to two different nodes of a doubly linked tree are given. Output the degree of relationship of the node P₁ to the node P₂ (the degree of relationship equals −1 if the node P₂ is not in the chain of ancestors of the node P₁; otherwise it equals L₁ − L₂, where L₁ and L₂ are the levels of nodes P₁ and P₂ respectively).

Tree53°. Pointers P₁ and P₂ to two different nodes of a doubly linked tree are given. Find the nearest mutual ancestor of the nodes P₁ and P₂ and output its pointer P₀.

Tree54. A pointer P₁ to the node of a doubly linked tree is given. Create a copy of the given tree and output a pointer P₂ to the root of the created tree.

Tree55. A pointer P₁ to the non-root node of a doubly linked tree is given. If the node P₁ 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₁ has no sibling then create it and all its descendants as a copy of the subtree with the root P₁. Output the pointer P₀ to the parent of P₁.

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₁ to the root of a nonempty tree is given. It the tree is a search tree, that is, values of its nodes form a non-decreasing sequence in inorder tree walk, then output nil; otherwise output the address of the first node (in inorder tree walk) that breaks the search-tree property.

Tree58. A pointer P₁ to the root of a nonempty tree is given. It the tree is a non-recurrent 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 search-tree property.

Tree59°. A pointer P₁ to the root of a nonempty non-recurrent search tree and an integer K are given. If the tree contains a node whose value equals K then output the address P₂ of this node, otherwise output nil. Also output the amount N of tree nodes that were checked during the search.

Tree60. A pointer P₁ 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₁ to the root of a search tree and an integer K are given (if the tree is empty then P₁ = 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₂ 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₁ to the root of a non-recurrent search tree and an integer K are given (if the tree is empty then P₁ = nil). Add a new node with the value K to the tree so that the tree still remains a non-recurrent search tree. Do not change the given tree if it already contains a node with the value K. Output the pointer P₂ 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₁ to the root of a search tree are given (if the tree is empty then P₁ = 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₂ 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₁ to the root of a non-recurrent search tree are given (if the tree is empty then P₁ = nil). Add N new nodes with values from the given sequence to the tree so that the tree still remains a non-recurrent search tree. Output the pointer P₂ 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₁ 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 non-recurrent search tree (use the recursive algorithm described in Tree62 to add each new node). Output the pointer P₁ 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₁ to the root of a nonempty search tree and P₂ to one of its nodes with no more than one child. Remove the node P₂ from the tree so that the tree still remains a search tree (if the node P₂ has a child then link the child with the parent of the node P₂). If the resulting tree is not empty then output the pointer P₃ to its root, otherwise output nil.

Tree68. Two pointers are given: P₁ to the root of a nonempty search tree and P₂ to one of its nodes with two children. Remove the node P₂ 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₂, then assign its value to the node P₂, 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₁ to the root of a nonempty search tree and P₂ to one of its nodes with two children. Remove the node P₂ 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₂, then assign its value to the node P₂, and finally remove the node P as in Tree67 (because the node P should have no more than one child).

Tree70°. A pointer P₁ to a node of a doubly linked search tree is given. Remove the node P₁ 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₂ to its root, otherwise output nil. If the node P₁ has two children then use the algorithm described in Tree68 for its removing.

Tree71. A pointer P₁ to a node of a doubly linked search tree is given. Remove the node P₁ 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₂ to its root, otherwise output nil. If the node P₁ 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):

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₁ 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):

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₁ 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 node-operator 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 parenthesis-free 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 node-operator 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 parenthesis-free postorder format):

<expression> ::= <digit> |
<expression> <expression> <operator>
<operator> ::= + | − | *

Tree79°. A pointer P₁ 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₁ 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₁ to the root of a nonempty parse tree is given. Output the string representation of expression that corresponds to the given tree. Use the parenthesis-free preorder format (see Tree77).

Tree82. A pointer P₁ to the root of a nonempty parse tree is given. Output the string representation of expression that corresponds to the given tree. Use the parenthesis-free 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 node-function 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₁ 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₁ 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₁ 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₂ to the root of the created general tree.

Tree87. A pointer P₁ 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₂ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ 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₁ to the root of a nonempty general tree is given. Output the pointer P₂ to the first node that has the maximal amount of child nodes. Use inorder tree walk (see Tree92).

Tree96. A pointer P₁ to the root of a nonempty general tree is given. Output the pointer P₂ to the last node that has the maximal sum of values of child nodes. Use postorder tree walk (see Tree93).

Tree97. A pointer P₁ 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₁ 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):

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₁ to the root of a nonempty general tree is given. Output the string that describes the tree using the representation specified in Tree99.

Last revised:
01.01.2024