Starting from the 4.15 version, Programming Taskbook contains two variants of this group. The new one, named GCTree, does not require to release resources used by the Node object because it is assumed that the Garbage Collector is used for this purpose. This difference occurs only for the tasks with the following numbers: 40–43, 55.

All numbers mentioned in tasks of this group are of integer type. All objects are of Node type; this class is defined in Programming Taskbook. In the tasks of this group the Data, Left, Right, and Parent properties of the Node class are used. Therefore one can assume that the Node class contains the following public members:

[PascalABC.NET]

// Constructors:
constructor Create;
constructor Create(aData: integer);
constructor Create(aLeft, aRight: Node; aData: integer);
constructor Create(aLeft, aRight: Node; aData: integer; aParent: Node);
// Properties (available to read and write):
property Data: integer;
property Left: Node;
property Right: Node;
property Parent: Node;
// Method that releases resources used by the Node object:
procedure Dispose;

[C#]

// Constructors:
public Node();
public Node(int aData);
public Node(Node aLeft, Node aRight, int aData);
public Node(Node aLeft, Node aRight, int aData, Node aParent);
// Properties (available to read and write):
public int Data;
public Node Left;
public Node Right;
public Node Parent;
// Method that releases resources used by the Node object:
public void Dispose();

[VB.NET]

' Constructors:
Public Sub New()
Public Sub New(aData As Integer)
Public Sub New(aLeft As Node, aRight As Node, _
aData As Integer)
Public Sub New(aLeft As Node, aRight As Node, _
aData As Integer, aParent As Node)
' Properties (available to read and write):
Public Property Data() As Integer
Public Property Left() As Node
Public Property Right() As Node
Public Property Parent() As Node
' Method that releases resources used by the Node object:
Public Sub Dispose() Implements IDisposable.Dispose

[F#]

// Constructors:
public new()
public new(aData: int)
public new(aLeft: Node, aRight: Node, aData: int)
public new(aLeft: Node, aRight: Node, aData: int, aParent: Node)
// Properties (available to read and write):
public Data: int
public Left: Node
public Right: Node
public Parent: Node
// Method that releases resources used by the Node object:
public Dispose()

[Java]

// Constructors:
Node();
Node(int aData);
Node(Node aLeft, Node aRight, int aData);
Node(Node aLeft, Node aRight, int aData, Node aParent);
// Accessors to properties:
int getData();
void setData(int value);
Node getLeft();
void setLeft(Node value);
Node getRight();
void setRight(Node value);
Node getParent();
void setParent(Node value);
// Method that releases resources used by the Node object:
void dispose();

[Python]

# Constructors:
Node(data = 0)
Node.for_tree(data = 0, left = None, right = None, parent = None)
# Properties (available to read and write):
Data
Left
Right
Parent
# Method that releases resources used by the Node object:
dispose()

[Ruby]

# Constructors:
Node.new()
Node.new(data)
Node.new(left, right, data)
Node.new(left, right, data, parent)
# Properties (available to read and write):
data
left
right
parent
# Method that releases resources used by the Node object:
dispose()

[Julia]

# Constructors:
node()
node(data::Integer)
node(left::Node, right::Node, data::Integer)
node(left::Node, right::Node, data::Integer, parent::Node)
# Accessors to properties (the ! symbol means changing the property):
data(node::Node)
data!(node::Node, value::Integer)
left(node::Node)
left!(node::Node, value::Node)
right(node::Node)
right!(node::Node, value::Node)
parent(node::Node)
parent!(node::Node, value::Node)
# Function that releases resources used by the Node object:
dispose!(node::Node)

In the most of the tasks only the Data, Left, and Right properties of the Node class are used. The Parent property is required in the tasks devoted to doubly linked trees.

The value of the Data property of a Node object is considered as the value of the corresponding tree node.

All these languages use the reference object model; that is, any object variable is a reference to the object instance. Therefore, the expression "output the reference to a tree node" means that you should output the value of a corresponding variable of the Node type.

In the most of the tasks only the Data, Left, and Right properties of the Node class are used. The Parent property is required in the tasks devoted to doubly linked trees.

The value of the Data property of a Node object is considered as the value of the corresponding tree node.

Binary trees: analysis

Tree1. An object A₁ of Node type is given. The object has public properties named Data (of integer type), Left and Right (of Node type). The Left and Right properties of the given object (a tree root) contain references to the left and right child nodes respectively. Output the Data properties of the tree root and its left and right children. Also output the references to the left and right child nodes.

Tree2°. An object A₁ of Node type (a tree root) is given. This object is linked by its Left and Right properties with objects of the same type (child nodes); they, in turn, are linked with their own child nodes and so on, until objects whose Left and Right properties are equal to null. Some of the nodes may have one property (Left or Right) equals null. Output the amount of tree nodes.

Tree3. A root A₁ of a nonempty tree and an integer K are given. Output the amount of nodes whose value equals K.

Tree4. A root A₁ of a nonempty tree is given. Output the sum of values of all tree nodes.

Tree5. A root A₁ of a nonempty tree is given. Output the amount of left child nodes (the tree root should not be counted).

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

Tree8. A root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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 root A₁ of a nonempty tree is given. Output the maximal value of the tree nodes and the amount of nodes with this value.

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

Tree22. A root A₁ 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 root A₁ of a nonempty tree is given. Using preorder tree walk, find the first tree node with the minimal value and output its reference A₂.

Tree24. A root A₁ of a nonempty tree is given. Using inorder tree walk, find the last node with the maximal odd value and output its reference A₂. If the tree does not contain nodes with odd values then output null.

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 reference to 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 reference to 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 reference to 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 reference to 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 reference to the tree root.

Tree30. An integer N (> 0) is given. 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 reference to 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 reference to 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 amount of nodes of its left subtree differs at most on 1 from the amount of nodes of its right subtree) and output the reference to 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 reference to 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 by means of the recursive algorithm described in Tree32.

Tree34°. An root A₁ of a nonempty tree is given. Create a copy of the tree and output the reference A₂ to its root.

Binary trees: changing

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

Tree36. A root A₁ of a nonempty tree is given. Halve the value of each tree node whose initial value is an even number.

Tree37. A root A₁ 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 root A₁ 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 properties of child nodes).

Tree39. A root A₁ 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 property).

Tree40°. A root A₁ of a nonempty tree is given. Remove all nodes from the tree (except the root) and call the Dispose method for each removed node (assign null to the Left and Right properties of the root).

Tree41. A root A₁ of a nonempty tree is given, the tree contains at least two nodes. Remove all tree leaves and assign null to the Left and Right properties of their parents. Call the Dispose method for each removed node.

Tree42. A root A₁ of a nonempty tree is given. Remove all nodes whose value is less than the root value, together with all their descendants. Call the Dispose method for each removed node.

Tree43. A root A₁ 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. Call the Dispose method for each removed node.

Tree44. A root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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. A node A₁ of a tree is given. It is an object of Node type that has public properties named Data (of integer type), Left, Right, and Parent (of Node type). The Left and Right properties contain references to the left and right child nodes respectively, the Parent property contains reference to the parent node (the Parent property of the root node equals null). Output references A_L and A_R to the left and right child of the given node, A₀ to its parent, and A₂ to its sibling (siblings are nodes that have the same parent). In some of required nodes are not exist then output null for each absent node.

Tree49°. A root A₁ of a tree is given. Tree nodes are represented by object of Node type; they are linked by the Left and Right properties of Node class. Using the Parent property of Node class, 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 properties) but also with its parent node (by the Parent property). The Parent property of the root node should be equal to null.

Tree50. A reference A₁ to some node of a doubly linked tree is given. Output the reference A₂ to the tree root.

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

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

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

Tree55. A reference A₁ to the non-root node of a doubly linked tree is given. If the node A₁ has a sibling then remove the sibling together with its descendants from the tree and call the Dispose method for each removed node. If the node A₁ has no sibling then create it and all its descendants as a copy of a the subtree with the root A₁. Output the reference A₀ to the parent of A₁.

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 reference to the tree root.

Binary search trees

Tree57. A root A₁ 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 null; otherwise output the reference to the first node (in inorder tree walk) that breaks the search-tree property.

Tree58. A root A₁ 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 null; otherwise output the reference to the first node (in inorder tree walk) that breaks the search-tree property.

Tree59°. A root A₁ 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 reference A₂ to this node, otherwise output null. Also output the amount N of tree nodes that were checked during the search.

Tree60. A root A₁ 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 root A₁ of a search tree and an integer K are given (if the tree is empty then P₁ = null). Add a new node with the value K to the tree so that the tree still remains a search tree. Output the reference A₂ to the root of the resulting tree. Use the following recursive algorithm for a tree with the root A: if A = null then create a leaf with the value K and assign the leaf reference to the object A; 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 root A₁ of a non-recurrent search tree and an integer K are given (if the tree is empty then A₁ = null). 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 reference A₂ to the root of the resulting tree. Use the following recursive algorithm for a tree with the root A: if A = null then create a leaf with the value K and assign the leaf reference to the object A; 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 the root A₁ of a search tree are given (if the tree is empty then A₁ = null). Add N new nodes with values from the given sequence to the tree so that the tree still remains a search tree. Output the reference A₂ 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 the root A₁ of a non-recurrent search tree are given (if the tree is empty then A₁ = null). 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 reference A₂ 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 reference A₁ 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 reference A₁ to the root of the created tree. Also output elements of the sorted sequence using the inorder tree walk.

Tree67. Two references are given: A₁ to the root of a nonempty search tree and A₂ to one of its nodes with no more than one child. Remove the node A₂ from the tree so that the tree still remains a search tree (if the node A₂ has a child then link the child with the parent of the node A₂). If the resulting tree is not empty then output the reference A₃ to its root, otherwise output null.

Tree68. Two references are given: A₁ to the root of a nonempty search tree and A₂ to one of its nodes with two children. Remove the node A₂ from the tree so that the tree still remains a search tree. Use the following algorithm: find the node A with the maximal value in the left subtree of the node A₂, then assign its value to the node A₂, and finally remove the node A as in Tree67 (because the node A should have no more than one child).

Tree69. Two references are given: A₁ to the root of a nonempty search tree and A₂ to one of its nodes with two children. Remove the node A₂ from the tree so that the tree still remains a search tree. Use the following algorithm: find the node A with the minimal value in the right subtree of the node A₂, then assign its value to the node A₂, and finally remove the node A as in Tree67 (because the node A should have no more than one child).

Tree70°. A reference A₁ to a node of a doubly linked search tree is given. Remove the node A₁ from the tree so that the tree still remains a doubly linked search tree. If the resulting tree is not empty then output the reference A₂ to its root, otherwise output null. If the node A₁ has two children then use the algorithm described in Tree68 for its removing.

Tree71. A reference A₁ to a node of a doubly linked search tree is given. Remove the node A₁ from the tree so that the tree still remains a doubly linked search tree. If the resulting tree is not empty then output the reference A₂ to its root, otherwise output null. If the node A₁ 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 reference to its root.

Tree73. A root A₁ 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 reference to its root.

Tree75°. A root A₁ 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 reference 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 reference 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 root A₁ 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 root A₁ 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 root A₁ 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 root A₁ 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 reference to the root of the created tree.

Tree84. A root A₁ 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 root A₁ 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 Node class as follows: the Left property of any node refers to its leftmost child whereas the Right property refers to the nearest right sibling of this node. The tree root has no siblings, therefore its Right property always equals null. A root A₁ of a nonempty binary tree is given. Create a general tree that corresponds to the given binary tree and output the reference A₂ to the root of the created general tree.

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

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

Tree97. A root A₁ of a nonempty general tree is given. In each set of siblings find the maximal value (that is, the maximal Data property) and assign this value to each node of the set.

Tree98. A root A₁ of a nonempty general tree is given. In each set of siblings inverse the order of the node values (that is, swap the Data properties of the first and the last sibling, then swap the Data properties 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 reference to its root.

Tree100. A root A₁ 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