BST-Search Which XXX completes the BST recursive search algorithm? BSTSearchRecursive(node, key) { if (node is not null) { if (key == node⇢key) return node XXX { return BSTSearchRecursive(node⇢right, key) else return BSTSearchRecursive(node⇢left, key) } return null } a. else if (node⇢right

Question

BST-Search

Which XXX completes the BST recursive search algorithm?

BSTSearchRecursive(node, key) {
   if (node is not null) {
      if (key == node⇢key)
         return node
      XXX {
         return BSTSearchRecursive(node⇢right, key)
      else
         return BSTSearchRecursive(node⇢left, key)
   }
   return null
}

a.
else if (node⇢right < key )
b.
else if (node⇢key < key)
c.
else if (node⇢right > key)
d.
else if (node⇢left < key )

BlackTom AI · Accepted Answer

Because in a BST all keys in the right subtree are greater than the current node's key, the algorithm should recurse to node->right when the search key is greater than node->key. Thus the missing condition is: else if (node->key < key). Relevant concepts: - Binary Search Tree (BST) invariant: for any node, every key in the left subtree is less than node->key, and every key in the right subtree is greater than node->key. - Recursive search logic: compare the target key to the current node's key; equal → found; larger → search right; smaller → search left. Step-by-step reasoning and examples: 1. Start at node with value node->key. 2. If node is null, return null (base case). 3. If key == node->key, return node (found). 4. If key > node->key, then by the BST invariant the target, if present, must lie in the right subtree, so call BSTSearchRecursive(node->right, key). Example: node->key = 10, key = 15 → 10 < 15 so recurse right. 5. Otherwise (key < node->key), recurse left: BSTSearchRecursive(node->left, key). Example: node->key = 10, key = 5 → 10 < 5 is false so go left. Why option b is correct: - Option b is "else if (node⇢key < key)" which exactly tests whether the search key is greater than the current node's key; if true, recurse on node->right, matching the BST property and intended control flow. Why the other options are incorrect: - a: "else if (node⇢right < key)" compares the right child pointer/value incorrectly; it uses the child reference instead of the node's key and is semantically wrong. - c: "else if (node⇢right > key)" again compares the right child rather than node->key and misstates the direction. - d: "else if (node⇢left < key)" compares the left child and would not correctly determine whether to go right or left. Conclusion: The correct choice is b (else if (node⇢key < key)), which matches the provided answer.

类似问题

BST Properties Below is a binary search tree of integers. Choose the correct statement 1: The largest number 2: The predecessor of S 3: The successor of G 4: The 2nd smallest number 5: The predecessor of A

BST-Rightmost/Leftmost Starting with an empty tree, build a BST by inserting nodes in the order 12, 101, 23, 48, 3, 33, 105, 2, 4 11. Which number will the rightmost node of the tree have? [Fill in the blank] Which number will the leftmost node of the tree have? [Fill in the blank]

BST-Search If the new node to be inserted is 270, it will be inserted as the _A_ child of node _B_ _A_= [ Select ] right left _B_ = [ Select ] 25 260 75 250 150 350

Binary-Search-Tree-Property Assume all the numbers in the following tree are unique integers. Choose the correct statements about the binary search tree.

BST-Review We can check if a binary tree T is a binary search tree as follows. Collect nodes in T by a in-order tree traversal into an ArrayList A. Check if all the nodes in A are in a ascending order.

BST-Property Which of the following rules does a valid BST follow?

In a Binary Search Tree, all elements below a given a node have values that are < that node's value.

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单