Bird
Raised Fist0
Data Structures Theoryknowledge~5 mins

Searching in BST in Data Structures Theory - Cheat Sheet & Quick Revision

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
Recall & Review
beginner
What is a Binary Search Tree (BST)?
A Binary Search Tree is a special type of binary tree where each node has at most two children. For every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property helps in efficient searching.
Click to reveal answer
beginner
How does searching work in a BST?
To search for a value, start at the root. If the value equals the root, you found it. If the value is smaller, search the left subtree. If larger, search the right subtree. Repeat until you find the value or reach a leaf node.
Click to reveal answer
intermediate
Why is searching in a BST efficient compared to a regular binary tree?
Because of the BST property, you can ignore half of the tree at each step. This reduces the search time to about log₂(n) steps on average, where n is the number of nodes, making it much faster than searching every node.
Click to reveal answer
beginner
What happens if the value is not found in the BST during search?
If the search reaches a leaf node without finding the value, it means the value is not in the tree. The search ends with a negative result.
Click to reveal answer
intermediate
What is the worst-case time complexity of searching in a BST?
In the worst case, the BST can become like a linked list (all nodes have only one child). Then, searching takes O(n) time, where n is the number of nodes.
Click to reveal answer
In a BST, if the value you are searching for is less than the current node's value, where do you search next?
AAt the current node again
BIn the right subtree
CIn the left subtree
DIn both subtrees
What is the average time complexity of searching in a balanced BST?
AO(log n)
BO(1)
CO(n log n)
DO(n)
If a BST has 15 nodes, approximately how many steps does it take to find a value on average?
A15 steps
B1 step
C30 steps
D4 steps
What does it mean if the search in a BST reaches a leaf node without finding the value?
AThe value is in the tree
BThe value is not in the tree
CThe tree is empty
DThe search should restart
What is the worst-case shape of a BST that causes slow searching?
ALinked list shape (all nodes have one child)
BComplete binary tree
CPerfectly balanced tree
DFull binary tree
Explain how searching for a value works in a Binary Search Tree.
Think about how the BST property guides the search direction.
You got /5 concepts.
    Describe why searching in a BST is generally faster than searching in a regular binary tree.
    Focus on how the BST structure helps reduce search steps.
    You got /4 concepts.

      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