Skip to content
Hello Python

Build and Query a Binary Search Tree

Practice ExerciseIntermediateMediumBinary Search TreeBinary TreeTree

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement bst_operations(values, queries). Insert values into a BST, ignoring duplicates. Return [inorder_values, query_results], where query_results contains one boolean per query.

Starter code

def bst_operations(values, queries):
    pass
Test cases

insert-search

{
  "args": [
    [
      5,
      3,
      7,
      2,
      4
    ],
    [
      4,
      6
    ]
  ]
}

Expected: [[2,3,4,5,7],[true,false]]

ignore-duplicates

{
  "args": [
    [
      2,
      1,
      2,
      3,
      1
    ],
    [
      1,
      2,
      4
    ]
  ]
}

Expected: [[1,2,3],[true,true,false]]

Wizard outline
  1. Step 1: Answer queries against an empty tree

    Represent an empty root and return false for every query when no values were inserted. The empty root is the base case shared by insertion, traversal, and search.

  2. Step 2: Seed the root node

    Turn the first inserted value into one root node with two empty child links. Every later insertion needs a concrete root from which comparisons can begin.

  3. Step 3: Insert nodes and traverse in order

    Build left and right child links, then collect values with an inorder traversal. Insertion plus inorder output makes the BST ordering invariant directly observable.

  4. Step 4: Search by the ordering invariant

    Direct each query left or right until it matches a node or reaches None. Directed lookup is the operational benefit of the BST invariant.

  5. Step 5: Ignore duplicate values

    Stop insertion when a value already matches the current node without changing the tree. An explicit equality branch prevents duplicates from drifting into the right subtree.

Footguns and prerequisites
  • Inserting equal values without a policy can create duplicate nodes or infinite loops.
  • Searching both subtrees discards the logarithmic benefit of a balanced BST.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Build a small explicit BST, traverse it in order, and direct each query left or right by comparison.

Why it works: Insertion preserves smaller values on the left and larger values on the right while ignoring equality. In-order traversal is therefore sorted, and directed search discards only subtrees that cannot contain the query.

def bst_operations(values, queries):
    root = None
    for value in values:
        if root is None:
            root = [value, None, None]
            continue
        node = root
        while True:
            if value == node[0]:
                break
            side = 1 if value < node[0] else 2
            if node[side] is None:
                node[side] = [value, None, None]
                break
            node = node[side]
    ordered = []
    def visit(node):
        if node is not None:
            visit(node[1])
            ordered.append(node[0])
            visit(node[2])
    visit(root)
    found = []
    for query in queries:
        node = root
        while node is not None and node[0] != query:
            node = node[1] if query < node[0] else node[2]
        found.append(node is not None)
    return [ordered, found]