Question 1

Consider the following binary search tree:  Which of the following sequences correctly represents an inorder traversal of this tree? 
A)A, C, H, G, E, N, P, M, J
B)J, E, M, C, G, P, A, H, N
C)A, C, E, G, H, J, M, N, P
D)J, E, C, A, G, H, M, P, N

Accepted Answer

An inorder traversal visits the left subtree first, then the root, and then the right subtree. Starting from the root, we can see that the left subtree contains nodes with keys less than 11eb9782_fe17_8930_b9fe_0db05a62d42a_TB7392_00 and the right subtree contains nodes with keys greater than 11eb9782_fe17_8930_b9fe_0db05a62d42a_TB7392_00.

Traversing the left subtree, we get to node C (key: 0dc882a4_2304_7acf_96ac_8114a4b4c4de_TB7392_00), then node A (key: 0df674f8_fdef_59c2_b612_1e6c1bb80647_TB7392_00). Moving back up to the root, we then visit node H (key: 173d6361_cb43_2dd7_0f23_75cff6d46c58_TB7392_00), followed by its left subtree containing nodes E (key: 1728fc5e_eb1d_63ce_5b28_8c1d289947d0_TB7392_00) and G (key: 173cbabf_0121_f05f_8a62_dd9dbdfeacc7_TB7392_00). Continuing on to the right subtree, we visit node N (key: 2b2f3c38_ea3d_457c_16f8_21db481a5857_TB7392_00) and its left subtree containing nodes M (key: 2b11f77f_1fc4_697a_76e7_210fd409bc94_TB7392_00) and J (key: 2b2f3c38_ea3d_457c_16f8_21db481a5857_TB7392_00). Finally, we visit node P (key: 2b11f77f_1fc4_697a_76e7_210fd409bc94_TB7392_00).

The correct order of keys is thus: A, C, E, G, H, J, M, N, P. The only option that represents this order is choice C.

Question 2

What are the differences between preorder, postorder, and inorder traversals?
A)Postorder only visits the right subtree.
B)The order of the root visit.
C)Preorder only visits the left subtree.
D)The order in which we visit the left and right subtrees.

Accepted Answer

The answer of What are the differences between preorder, postorder,...

Question 3

If the postorder traversal of an expression tree is 8, 2, +, 5, /, what is the preorder traversal?
A)/, +, 2, 8, 5
B)8, +, 2, /, 5
C)/, +, 8, 2, 5
D)+, /, 8, 2, 5

Accepted Answer

In an expression tree, the postorder traversal lists operands first, followed by their operators. To find the preorder traversal, we start with the last operator in the postorder as the root. The postorder given is 8, 2, +, 5, /, indicating that '/' is the root operator. The expression before '/' (8, 2, +) forms the left subtree, and '5' is the right subtree. The left subtree, when reconstructed, has '+' as the root with '8' and '2' as leaves. Therefore, the preorder traversal starts with the root '/', followed by the root of the left subtree '+', then its leaves '8' and '2', and finally the right subtree '5', making the correct preorder traversal /, +, 8, 2, 5.

Question 4

You wish to traverse a binary search tree in sorted order.Arrange the following actions in the correct order to accomplish this.
i.Print the right subtree recursively
II.Print the root
III.Print the left subtree recursively
A)I, II, III
B)II, III, I
C)III, I, II
D)III, II, I

Accepted Answer

To traverse a binary search tree in sorted order, you should first print the left subtree recursively (to handle all smaller elements), then print the root (the current element), and finally print the right subtree recursively (to handle all larger elements). This is known as an in-order traversal.

Question 5

Locating an element in an unbalanced binary search tree takes ____ time. A)O(n) B)O(n²) C)O(1) D)O(log (n))

Accepted Answer

In the worst case, an unbalanced binary search tree can degenerate into a linked list, making the time complexity for searching an element O(n).

Question 6

Removing an element from an unbalanced binary search tree takes ____ time. A)O(log (n)) B)O(n) C)O(1) D)O(n²)

Accepted Answer

Removing an element from an unbalanced binary search tree can take up to O(n) time in the worst case scenario if the tree is completely unbalanced and degenerates into a linked list.

Question 7

Which of the following statements about the three tree traversal schemes studied is correct?
A)Preorder traversal is used for evaluating arithmetic expression trees on a stack-based calculator.
B)Postorder traversal is used for evaluating arithmetic expression trees on a stack-based calculator.
C)Preorder traversal is used for removing file directories by removing subdirectories first.
D)Postorder traversal is used for copying file directories.

Accepted Answer

Postorder traversal is used for evaluating arithmetic expression trees on a stack-based calculator. This is because in postorder traversal, the operands are always encountered before their corresponding operators, which makes it suitable for computing arithmetic expressions. The other options are not true.

Question 8

Consider the following binary search tree:  Which of the following sequences correctly represents a postorder traversal of this tree? 
A)J, E, C, A, G, H, M, P, N
B)J, E, M, C, G, P, A, H, N
C)A, C, E, G, H, J, M, N, P
D)A, C, H, G, E, N, P, M, J

Accepted Answer

The answer of Consider the following binary search tree: ...

Question 9

Which of the following statements about the three tree traversal schemes studied is correct?
A)Inorder traversal is used for copying file directories.
B)Postorder traversal is used for copying file directories.
C)Postorder traversal is used for removing file directories by removing subdirectories first.
D)Inorder traversal is used for evaluating arithmetic expression trees on a stack-based calculator.

Accepted Answer

C) Postorder traversal is indeed used for removing file directories by removing subdirectories first. This ensures that a directory is deleted only after all its contents, including files and subdirectories, have been deleted, which is a necessary condition for directory removal in many file systems.

Question 10

Given the BinarySearchTree and Node classes (partially shown below), select an expression to complete the recursive method smallest in the Node class.The method returns the smallest data value in the binary search tree rooted at a node.  
A)right.smallest()
B)left.smallest()
C)Math.min(left.smallest(), right.smallest())
D)data.smallest()

Accepted Answer

Since the binary search tree follows the property of having smaller values on the left subtree and larger values on the right subtree, the smallest value will always be located in the leftmost subtree. Therefore, the correct expression to return the smallest value is to recursively call the smallest method on the left Node object, which is represented by the expression 'left.smallest()'.

Question 11

You wish to traverse a binary search tree using preorder traversal.Arrange the following actions in the correct order to accomplish this.
i.Print the right subtree recursively
II.Print the root
III.Print the left subtree recursively
A)II, III, I
B)II, I, III
C)I, II, III
D)III, I, II

Accepted Answer

The correct order for preorder traversal is to visit the root first (II), then recursively traverse the left subtree (III), and finally, traverse the right subtree (I).

Question 12

Consider the following binary search tree:  Which of the following sequences correctly represents a preorder traversal of this tree? 
A)J, E, M, C, G, P, A, H, N
B)J, E, C, A, G, H, M, P, N
C)A, C, H, G, E, N, P, M, J
D)A, C, E, G, H, J, M, N, P

Accepted Answer

The answer of Consider the following binary search tree: ...

Question 13

Adding an element to an unbalanced binary search tree takes ____ time. A)O(n) B)O(1) C)O(log (n)) D)O(n²)

Accepted Answer

Adding an element to an unbalanced binary search tree can take O(n) time in the worst case, where n is the number of nodes in the tree. This worst-case scenario occurs when the tree becomes a linear chain of nodes (degenerates into a linked list), requiring a traversal through all the nodes to insert a new element at the correct position.

Question 14

You wish to traverse a binary search tree using postorder traversal.Arrange the following actions in the correct order to accomplish this.
i.Print the right subtree recursively
II.Print the root
III.Print the left subtree recursively
A)III, II, I
B)I, III, II
C)III, I, II
D)I, II, III

Accepted Answer

Postorder traversal involves visiting the left subtree recursively, then the right subtree recursively, and finally the root. Therefore, the correct order is to first print the left subtree recursively, then print the right subtree recursively, and finally print the root. So the correct order is III, I, II, which is given in option C.

Question 15

Which of the following statements about breadth-first and depth-first traversal is NOT correct?
A)Depth-first search goes deeply into the tree and then backtracks when it reaches the leaves.
B)Breadth-first and depth-first search only work on a binary tree.
C)Breadth-first search first visits all nodes on the same level before visiting the children.
D)Depth-first search uses a stack to track the nodes that it visits.

Accepted Answer

Breadth-first and depth-first search can be performed on any type of tree, not just binary trees.

Question 16

Assuming that the variable t is instantiated to an empty BinarySearchTree, select a statement to complete the following code segment, so that the resulting binary search tree has a height of 4.  
A)t.add("your");
B)t.add("the");
C)t.add("his");
D)t.add("my");

Accepted Answer

The answer of Assuming that the variable t is instantiated...

Question 17

Removing an element from a balanced binary search tree takes ____ time. A)O(1) B)O(log (n)) C)O(n²) D)O(n)

Accepted Answer

Removing an element from a balanced binary search tree takes O(log(n)) time, as we need to first search for the node to be removed which takes O(log(n)) time in a balanced tree. The actual removal process of the node takes constant time. Therefore, the overall time complexity is O(log(n)).

Question 18

Given the Visitor interface discussed in section 17.4 (shown below), select a statement to complete the class CodeFinder.The class is to be used when traversing a binary tree while displaying every data value that contains the code "007".  
A)data.toString().indexOf("007") > 0
B)data.equals("007")
C)data.toString().indexOf("007") >= 0
D)data.contains("007")

Accepted Answer

The indexOf() method returns -1 if the specified string is not found. Therefore, in order to ensure that all values containing "007" are captured, we should use the greater than or equal to operator (>=) instead of the greater than operator (>), which would exclude values at index 0. The contains() method is not available for strings in Java, so option D is incorrect. Option A would not correctly capture values at the beginning of the string, such as "007Agent", so it is also incorrect. Option B would only capture exact matches to the string "007", so it is too restrictive.

Question 19

If the postorder traversal of an expression tree is 8, 2, +, 5, /, what is the numeric result of that Reverse Polish Notation expression?
A)8
B)2
C)7
D)15

Accepted Answer

The answer of If the postorder traversal of an expression...

Question 20

If the postorder traversal of an expression tree is, 8, 2, +, 5, /, what is the result of an inorder traversal?
A)+, /, 8, 2, 5
B)8, +, 2, /, 5
C)/, +, 2, 8, 5
D)/, +, 8, 2, 5

Accepted Answer

Inorder traversal of a binary expression tree visits the left subtree, then the node itself, and finally the right subtree. Thus, the inorder traversal of the given expression tree will be: (8 + 2) / 5, which equals to 2.

Quiz 17: Tree Structures

Consider the following binary search tree: Which of the following sequences correctly represents an inorder traversal of this tree?

What are the differences between preorder, postorder, and inorder traversals?

If the postorder traversal of an expression tree is 8, 2, +, 5, /, what is the preorder traversal?

You wish to traverse a binary search tree in sorted order.Arrange the following actions in the correct order to accomplish this. i.Print the right subtree recursively II.Print the root III.Print the left subtree recursively

Locating an element in an unbalanced binary search tree takes ____ time.

Removing an element from an unbalanced binary search tree takes ____ time.

Which of the following statements about the three tree traversal schemes studied is correct?

Consider the following binary search tree: Which of the following sequences correctly represents a postorder traversal of this tree?

Which of the following statements about the three tree traversal schemes studied is correct?

Given the BinarySearchTree and Node classes (partially shown below) , select an expression to complete the recursive method smallest in the Node class.The method returns the smallest data value in the binary search tree rooted at a node.

You wish to traverse a binary search tree using preorder traversal.Arrange the following actions in the correct order to accomplish this. i.Print the right subtree recursively II.Print the root III.Print the left subtree recursively

Consider the following binary search tree: Which of the following sequences correctly represents a preorder traversal of this tree?

Adding an element to an unbalanced binary search tree takes ____ time.

You wish to traverse a binary search tree using postorder traversal.Arrange the following actions in the correct order to accomplish this. i.Print the right subtree recursively II.Print the root III.Print the left subtree recursively

Which of the following statements about breadth-first and depth-first traversal is NOT correct?

Assuming that the variable t is instantiated to an empty BinarySearchTree, select a statement to complete the following code segment, so that the resulting binary search tree has a height of 4.

Removing an element from a balanced binary search tree takes ____ time.

Given the Visitor interface discussed in section 17.4 (shown below) , select a statement to complete the class CodeFinder.The class is to be used when traversing a binary tree while displaying every data value that contains the code "007".

If the postorder traversal of an expression tree is 8, 2, +, 5, /, what is the numeric result of that Reverse Polish Notation expression?

If the postorder traversal of an expression tree is, 8, 2, +, 5, /, what is the result of an inorder traversal?