Bird
Raised Fist0
Data Structures Theoryknowledge~20 mins

Searching in BST in Data Structures Theory - Practice Problems & Coding Challenges

Choose your learning style10 modes available
LearnWhyDeepVisualPracticeChallengeProjectRecallTime

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
Challenge - 5 Problems
🎖️
BST Search Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
🧠 Conceptual
intermediate
2:00remaining
How does searching work in a Binary Search Tree?

Imagine you want to find a number in a Binary Search Tree (BST). What is the main idea behind the search process?

ARandomly pick nodes and check if the number matches until found.
BStart at any leaf and move upwards comparing values until the number is found.
CStart at the root, compare the number, then go left if smaller or right if larger, repeating until found or no child exists.
DSearch all nodes in the tree one by one from left to right until the number is found.
Attempts:
2 left
💡 Hint

Think about how the BST organizes values to help find numbers quickly.

📋 Factual
intermediate
2:00remaining
What is the worst-case time complexity of searching in a BST?

Consider a Binary Search Tree with n nodes. What is the worst-case time complexity to search for a value?

AO(n), when the tree is skewed like a linked list.
BO(log n), always regardless of tree shape.
CO(1), because BSTs allow instant access.
DO(n log n), due to repeated comparisons.
Attempts:
2 left
💡 Hint

Think about what happens if the tree is not balanced.

🚀 Application
advanced
2:00remaining
Find the node in the BST after searching for 15

Given the BST below, what node will the search end on when looking for the value 15?

Tree structure (each node: value):

  • Root: 10
  • Left child of 10: 5
  • Right child of 10: 20
  • Left child of 20: 15
  • Right child of 20: 25
ANode with value 20
BNode with value 15
CNode with value 10
DNode with value 25
Attempts:
2 left
💡 Hint

Follow the BST search steps comparing 15 with each node value.

🔍 Analysis
advanced
2:00remaining
What happens if you search for a value not in the BST?

Consider searching for the value 13 in the BST below:

  • Root: 10
  • Left child of 10: 5
  • Right child of 10: 20
  • Left child of 20: 15
  • Right child of 20: 25

What is the result of the search?

AThe search loops infinitely because 13 is not found.
BThe search returns the root node 10 as the closest value.
CThe search returns the node with value 15 as the closest match.
DThe search ends at a leaf node where the value would be if it existed, confirming 13 is not in the tree.
Attempts:
2 left
💡 Hint

Think about how the search moves down the tree and what happens when it can't go further.

❓ Reasoning
expert
2:00remaining
How does tree balance affect search efficiency in BST?

Why does balancing a BST improve the efficiency of searching compared to an unbalanced BST?

ABalancing keeps the tree height low, making the maximum search steps close to log(n), speeding up search.
BBalancing increases the number of nodes, so searching takes longer.
CBalancing removes nodes, so fewer values can be searched.
DBalancing changes the node values to be sorted in a list, not a tree.
Attempts:
2 left
💡 Hint

Consider how the height of the tree relates to the number of steps in searching.

Practice

(1/5)
1. What is the main advantage of searching in a Binary Search Tree (BST)?
easy
A. It allows faster search by using the order of elements
B. It stores elements in random order for quick access
C. It uses hashing to find elements instantly
D. It searches all nodes one by one sequentially

Solution

  1. Step 1: Understand BST property

    A BST keeps elements ordered so smaller values are on the left and larger on the right.

  2. Step 2: Use order for searching

    This order lets us decide to go left or right, skipping half the tree each step, making search faster.

  3. Final Answer:

    It allows faster search by using the order of elements -> Option A

  4. Quick Check:

    BST order speeds search = It allows faster search by using the order of elements [OK]
Hint: BST order guides search direction quickly [OK]
Common Mistakes:
  • Thinking BST stores elements randomly
  • Confusing BST with hashing
  • Assuming linear search in BST
2. Which of the following is the correct way to decide the next node to visit when searching for a value in a BST?
easy
A. Go left if target is greater than current node
B. Go left if target is smaller than current node
C. Go right if target is smaller than current node
D. Always go to the root node

Solution

  1. Step 1: Recall BST search rule

    If the target is smaller than the current node's value, we move to the left child.

  2. Step 2: Apply rule to options

    Go left if target is smaller than current node correctly states to go left if target is smaller, which matches BST property.

  3. Final Answer:

    Go left if target is smaller than current node -> Option B

  4. Quick Check:

    Smaller target -> left child = Go left if target is smaller than current node [OK]
Hint: Smaller target means go left in BST [OK]
Common Mistakes:
  • Reversing left and right directions
  • Ignoring BST ordering rules
  • Always going to root node
3. Consider the BST below:
      15
     /  \
    10  20
   /    / \
  8    17 25

Which nodes will be visited when searching for the value 17?
medium
A. [10, 8, 17]
B. [15, 10, 8]
C. [15, 20, 25]
D. [15, 20, 17]

Solution

  1. Step 1: Start at root and compare with 17

    Root is 15. Since 17 > 15, move right to 20.

  2. Step 2: Compare 20 with 17

    17 < 20, so move left to 17, which matches the target.

  3. Final Answer:

    [15, 20, 17] -> Option D

  4. Quick Check:

    Path to 17 = 15 -> 20 -> 17 [OK]
Hint: Follow BST rules: left if smaller, right if larger [OK]
Common Mistakes:
  • Going left from 15 when target is larger
  • Skipping nodes in path
  • Confusing node values
4. You wrote code to search a BST but it always returns None even when the value exists. What is the most likely mistake?
medium
A. Not moving to left child when target is smaller
B. Using a queue instead of recursion
C. Always moving to left child regardless of target
D. Checking only the root node

Solution

  1. Step 1: Understand BST search logic

    Search must move left if target is smaller, right if larger.

  2. Step 2: Identify error in always moving left

    If code always moves left, it misses nodes on the right side where target might be.

  3. Final Answer:

    Always moving to left child regardless of target -> Option C

  4. Quick Check:

    Wrong direction causes search failure = Always moving to left child regardless of target [OK]
Hint: Move left or right based on comparison, not always left [OK]
Common Mistakes:
  • Ignoring right subtree
  • Checking only root node
  • Using wrong data structure for traversal
5. Given a BST where some nodes have duplicate values on the right subtree, how should the search algorithm be adapted to find all occurrences of a target value?
hard
A. Traverse both left and right subtrees when node equals target
B. Search left subtree only once target is found
C. Stop search immediately after first match
D. Ignore duplicates and return first found

Solution

  1. Step 1: Understand duplicates in BST

    Duplicates are stored in right subtree, so multiple matches can exist there.

  2. Step 2: Adapt search to find all matches

    When a node equals target, search both left (for smaller) and right (for duplicates) subtrees to find all occurrences.

  3. Final Answer:

    Traverse both left and right subtrees when node equals target -> Option A

  4. Quick Check:

    Check both sides for duplicates = Traverse both left and right subtrees when node equals target [OK]
Hint: Check both subtrees when value matches to find duplicates [OK]
Common Mistakes:
  • Stopping after first match
  • Ignoring right subtree duplicates
  • Searching only one subtree