Trees (based on objects)
Binary trees: analysis
Tree1. An object A_{1} 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_{1} 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_{1} of a nonempty tree and an integer K are given. Output the amount of nodes whose value equals K.
Tree4. A root A_{1} of a nonempty tree is given. Output the sum of values of all tree nodes.
Tree5. A root A_{1} of a nonempty tree is given. Output the amount of left child nodes (the tree root should not be counted).
Tree6°. A root A_{1} 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_{1} of a nonempty tree is given. Output the sum of values of all tree leaves.
Tree8. A root A_{1} 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_{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 root A_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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 root A_{1} 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_{1} 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_{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 root A_{1} of a nonempty tree is given. Output the minimal value of its leaves.
Tree22. A root A_{1} 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_{1} of a nonempty tree is given. Using preorder tree walk, find the first tree node with the minimal value and output its reference A_{2}.
Tree24. A root A_{1} of a nonempty tree is given. Using inorder tree walk, find the last node with the maximal odd value and output its reference A_{2}. 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 Ldepth 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_{1} of a nonempty tree is given. Create a copy of the tree and output the reference A_{2} to its root.
Binary trees: changing
Tree35. A root A_{1} of a nonempty tree is given. Double the value of each tree node.
Tree36. A root A_{1} of a nonempty tree is given. Halve the value of each tree node whose initial value is an even number.
Tree37. A root A_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{0} to its parent, and A_{2} 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_{1} 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_{1} to some node of a doubly linked tree is given. Output the reference A_{2} to the tree root.
Tree51. References 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. References A_{1} and A_{2} to two different nodes of a doubly linked tree are given. Output the degree of relationship of the node A_{1} to the node A_{2} (the degree of relationship equals −1 if the node A_{2} is not in the chain of ancestors of the node A_{1}; otherwise it equals L_{1} − L_{2}, where L_{1} and L_{2} are the levels of nodes A_{1} and A_{2} respectively).
Tree53°. References A_{1} and A_{2} to two different nodes of a doubly linked tree are given. Find the nearest mutual ancestor of the nodes A_{1} and A_{2} and output its reference A_{0}.
Tree54. A reference A_{1} to the node of a doubly linked tree is given. Create a copy of the given tree and output a reference A_{2} to the root of the created tree.
Tree55. A reference A_{1} to the nonroot node of a doubly linked tree is given. If the node A_{1} 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_{1} has no sibling then create it and all its descendants as a copy of a the subtree with the root A_{1}. Output the reference A_{0} to the parent of A_{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 reference to the tree root.
Binary search trees
Tree57. A root A_{1} 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 null; otherwise output the reference to the first node (in inorder tree walk) that breaks the searchtree property.
Tree58. A root A_{1} 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 null; otherwise output the reference to the first node (in inorder tree walk) that breaks the searchtree property.
Tree59°. A root A_{1} 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 reference A_{2} to this node, otherwise output null. Also output the amount N of tree nodes that were checked during the search.
Tree60. A root A_{1} 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_{1} of a search tree and an integer K are given (if the tree is empty then P_{1} = 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_{2} 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_{1} of a nonrecurrent search tree and an integer K are given (if the tree is empty then A_{1} = null). 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 reference A_{2} 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_{1} of a search tree are given (if the tree is empty then A_{1} = 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_{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 the root A_{1} of a nonrecurrent search tree are given (if the tree is empty then A_{1} = null). 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 reference A_{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 reference A_{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 reference A_{1} 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_{1} to the root of a nonempty search tree and A_{2} to one of its nodes with no more than one child. Remove the node A_{2} from the tree so that the tree still remains a search tree (if the node A_{2} has a child then link the child with the parent of the node A_{2}). If the resulting tree is not empty then output the reference A_{3} to its root, otherwise output null.
Tree68. Two references are given: A_{1} to the root of a nonempty search tree and A_{2} to one of its nodes with two children. Remove the node A_{2} 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_{2}, then assign its value to the node A_{2}, 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_{1} to the root of a nonempty search tree and A_{2} to one of its nodes with two children. Remove the node A_{2} 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_{2}, then assign its value to the node A_{2}, and finally remove the node A as in Tree67 (because the node A should have no more than one child).
Tree70°. A reference A_{1} to a node of a doubly linked search tree is given. Remove the node A_{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 reference A_{2} to its root, otherwise output null. If the node A_{1} has two children then use the algorithm described in Tree68 for its removing.
Tree71. A reference A_{1} to a node of a doubly linked search tree is given. Remove the node A_{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 reference A_{2} to its root, otherwise output null. If the node A_{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 reference to its root.
Tree73. A root A_{1} 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 reference to its root.
Tree75°. A root A_{1} 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 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 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 reference 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 reference 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 root A_{1} 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_{1} 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_{1} 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 root A_{1} 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 reference to the root of the created tree.
Tree84. A root A_{1} 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_{1} 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_{1} of a nonempty binary tree is given. Create a general tree that corresponds to the given binary tree and output the reference A_{2} to the root of the created general tree.
Tree87. A root A_{1} 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_{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 root A_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} 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_{1} of a nonempty general tree is given. Output the reference A_{2} to the first node that has the maximal amount of child nodes. Use inorder tree walk (see Tree92).
Tree96. A root A_{1} of a nonempty general tree is given. Output the reference A_{2} to the last node that has the maximal sum of values of child nodes. Use postorder tree walk (see Tree93).
Tree97. A root A_{1} 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_{1} 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): <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 reference to its root.
Tree100. A root A_{1} of a nonempty general tree is given. Output the string that describes the tree using the representation specified in Tree99.
