Data Structure1 Practice4 Interview

Binary Search Tree

GuideCode Labs

Binary tree maintaining an ordering invariant for search, insertion, and range traversal. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Binary Search Tree when the prompt's constraints and required operations match this shape: Binary tree maintaining an ordering invariant for search, insertion, and range traversal.

On this page · Mental Model

Checking your account…

Mental Model

A binary search tree adds order to binary-tree shape. Under a strict no-duplicates policy, every value in a node’s left subtree is smaller and every value in its right subtree is larger. This is a global ancestor constraint, not merely a comparison with each immediate child.

Ordering Is a Global Invariant

Each descent narrows an allowed interval. Going left replaces the upper bound with the current value; going right replaces the lower bound. A descendant must satisfy every bound inherited from all ancestors. Inorder traversal visits a valid BST in sorted order, but sorted output alone does not identify the original shape.

Build and Query by Comparison

Search and insertion compare once per visited level, discarding the impossible subtree. Their cost is O(h), where h is tree height: O(log n) when balanced and O(n) for a chain created by sorted insertions. Python does not provide a built-in mutable BST; the bisect module(opens in a new tab) serves sorted lists and has different insertion costs.

Build and Query a BST

Reference

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]

Practice

Implement bst_operations(values, queries). Insert unique values, then return inorder values and directed-search results.

def bst_operations(values, queries):
    ordered = sorted(set(values))
    return [ordered, [False for _ in queries]]

Public tests

Verify insertion and directed queries

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Validate with Ancestor Bounds

Checking left < node < right for immediate children misses a value that violates a higher ancestor. Pass lower and upper bounds through recursion. Decide duplicate policy explicitly; the strict contract uses open bounds, so equality is invalid anywhere.

Validate Ancestor Bounds

Reference

def is_valid_bst(level_order):
    def valid(index, lower, upper):
        if index >= len(level_order) or level_order[index] is None:
            return True
        value = level_order[index]
        if not lower < value < upper:
            return False
        return valid(2 * index + 1, lower, value) and valid(2 * index + 2, value, upper)
    return valid(0, float('-inf'), float('inf'))

Practice

Implement is_valid_bst(level_order) for a complete-index array. Require strict ordering against all ancestor lower and upper bounds.

def is_valid_bst(level_order):
    for index, value in enumerate(level_order):
        if value is None:
            continue
        left, right = 2 * index + 1, 2 * index + 2
        if left < len(level_order) and level_order[left] is not None and level_order[left] >= value:
            return False
        if right < len(level_order) and level_order[right] is not None and level_order[right] <= value:
            return False
    return True

Public tests

Reject nonlocal ordering violation

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose BST or Binary Search

Use a BST when the input is already a tree or dynamic ordered operations are central. Use binary search on a sorted list for compact static data and frequent reads; insertion into the middle still costs O(n). Use a hash map for exact-key lookup without range or order queries, and a heap when only the current extreme matters.

Common Pitfalls

Validating only parent-child pairs ignores ancestor bounds.
Claiming O(log n) without a balance guarantee hides the O(n) worst case.
Inorder traversal does not prove strict validity when duplicate policy is unspecified.
Deleting a two-child node requires a consistent successor/predecessor replacement and relink.

Explain It in an Interview

State the duplicate rule and the interval owned by each recursive call. For search, name the subtree discarded by each comparison. Give complexity in terms of height first, then translate to balanced and worst-case bounds. Do not call every binary tree a BST.

Build and Query a Binary Search Tree(opens in a new tab) practices directed descent. Validate a Binary Search Tree(opens in a new tab) tests the global lower/upper-bound invariant.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Binary Search Tree itself is taught as an interview abstraction.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Core Binary Search Tree workflow	`O((n + q)h)`	`O((n + q)h)`	Build a small explicit BST, traverse it in order, and direct each query left or right by comparison.

Space

O(n + h) for the demonstrated Binary Search Tree workflow.

Assumptions

State the concrete operation and representation before claiming a bound; tree height and graph density can change it.
The bound counts the operations in Build and Query a Binary Search Tree and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

State the precise Binary Search Tree invariant before coding and preserve it after every update, traversal step, or recursive return.
Preserve the BST ordering invariant during insertion. This remains true after every accepted operation.
Use in-order traversal for sorted output and the same comparisons for search. This remains true after every accepted operation.

When To Use Or Avoid Binary Search Tree

Use It When

Use Binary Search Tree when its representation directly supports the prompt's repeated query or update.
Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Binary Search Tree invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def bst_operations(values, queries):
    pass

Use instead

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]

Where you will hit this: Build and Query a Binary Search Tree(opens in a new tab)

Breaking the central invariant

Always sends equality right, so duplicate input values appear more than once in the traversal.

Prevent it: Keep this invariant visible while editing: State the precise Binary Search Tree invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def bst_operations(values, queries):
    return [sorted(values), [query in values for query in queries]]

Use instead

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]

Where you will hit this: Build and Query a Binary Search Tree(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O((n + q)h).

Avoid

def bst_operations(values, queries):
    return [sorted(values), [query in values for query in queries]]

Use instead

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]

Where you will hit this: Validate a Binary Search Tree(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python bisect — Array Bisection Algorithm(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…