A Binary Search Tree (BST) is a binary tree with an additional ordering invariant:

all keys in left subtree < node.key < all keys in right subtree

The exact duplicate policy should be clarified if duplicates are allowed.

The source material places Chapter 14 — BST immediately after Sorting and before the advanced algorithmic chapters. It identifies search, insert, delete, minimum, maximum, successor, and predecessor as core BST operations, with O(log n) behavior when the tree is height-balanced and O(n) in the worst case.

1. What Part 14 Is Really Teaching

Don’t approach BSTs as:

“I need to memorize tree insertion and deletion.”

Instead think:

BST
 ↓
Ordering invariant
 ↓
Eliminate irrelevant subtrees
 ↓
Search / insert / delete

The fundamental idea is:

Use ordering to avoid visiting irrelevant parts of the tree.

This connects directly to Part 11 — Searching.

Sorted array
    ↓
Binary search

Ordered tree
    ↓
BST search

Both exploit:

Ordering
   ↓
Candidate elimination

2. Binary Tree vs Binary Search Tree

A binary tree only defines:

       node
       /  \
    left  right

A BST additionally requires:

left subtree < node < right subtree

Example:

          10
        /    \
       5      15
      / \    /  \
     2   7  12  20

This is a valid BST.

The source’s broader interview guide explicitly identifies BST knowledge as including search, insert, delete, min, max, successor, predecessor, recursion, and iterative traversal.

3. The Most Important BST Invariant

The most useful invariant is:

Every node must respect the lower and upper bounds imposed by all of its ancestors.

Checking only immediate children is not enough.

Consider:

7 < 15, so the local relationship looks valid.

But 7 is in the right subtree of 10, so it must satisfy:

7 > 10

It does not.

Therefore the tree is not a valid BST.

4. Validating a BST

Use inherited bounds.

def is_bst(root):
    def check(node, low, high):
        if node is None:
            return True

        if not (low < node.data < high):
            return False

        return (
            check(node.left, low, node.data)
            and check(node.right, node.data, high)
        )

    return check(root, float("-inf"), float("inf"))

Complexity:

Time:  O(n)
Space: O(h)

where h is tree height.

The source emphasizes that recursion depth contributes to space complexity: a balanced tree has roughly O(log n) recursion depth, while a skewed tree can require O(n).

5. Why Inorder Traversal Works

For a BST:

Inorder = Left → Root → Right

produces keys in sorted order.

Example:

          10
        /    \
       5      15
      / \    /  \
     2   7  12  20

Inorder:

2 5 7 10 12 15 20

The source explicitly notes this property of BSTs.

Therefore another validation strategy is:

inorder traversal
       ↓
must be strictly increasing

The bounds approach, however, makes the invariant especially explicit.

6. BST Search

Suppose:

          10
        /    \
       5      15
      / \    /  \
     2   7  12  20

Search for 12.

At 10:

12 > 10

Therefore the entire left subtree can be discarded.

At 15:

12 < 15

Therefore the right subtree of 15 can be discarded.

Move left and find 12.

The search never needs to examine irrelevant nodes.

7. Python BST Search

def search_bst(root, target):
    current = root

    while current:
        if target == current.data:
            return current

        if target < current.data:
            current = current.left
        else:
            current = current.right

    return None

Complexity:

Time:  O(h)
Space: O(1)

For a balanced BST:

h = O(log n)

so:

Search = O(log n)

For a skewed BST:

h = O(n)

so:

Search = O(n)

The source explicitly emphasizes this balanced-versus-skewed distinction.

8. BST Search vs Binary Search

Structure	Search	Dynamic Updates
Sorted array	`O(log n)`	Expensive
Balanced BST	`O(log n)`	`O(log n)`
Skewed BST	`O(n)`	`O(n)`

The deeper distinction is:

Sorted array
→ excellent static queries

Balanced BST
→ ordered queries + dynamic updates

9. BST Insertion

To insert a key:

start at root
    ↓
compare
    ↓
go left/right
    ↓
continue until empty position
    ↓
insert

Example: insert 13.

13 > 10 → right
13 < 15 → left
13 > 12 → right

So 13 becomes the right child of 12.

def insert_bst(root, value):
    if root is None:
        return BinaryTreeNode(value)

    current = root

    while True:
        if value < current.data:
            if current.left is None:
                current.left = BinaryTreeNode(value)
                break
            current = current.left
        else:
            if current.right is None:
                current.right = BinaryTreeNode(value)
                break
            current = current.right

    return root

Complexity:

Time:  O(h)
Space: O(1)

10. Duplicates Need a Policy

Ask:

“Are duplicate keys allowed?”

If yes, define a consistent rule:

duplicates → left

or:

duplicates → right

Then use the same rule during validation, insertion, and deletion.

This is exactly the kind of clarification expected in a strong coding interview. The source recommends clarifying input assumptions, duplicates, edge cases, and expected complexity before coding.

11. Minimum and Maximum

BST structure makes these operations simple.

Minimum:

keep going left

Maximum:

keep going right

def find_min(root):
    if root is None:
        return None

    current = root

    while current.left:
        current = current.left

    return current

def find_max(root):
    if root is None:
        return None

    current = root

    while current.right:
        current = current.right

    return current

Both take:

O(h)

12. Successor

The inorder successor is the smallest key greater than the current node.

Two cases exist.

Case 1 — Right subtree exists

successor =
minimum of right subtree

Case 2 — No right subtree

Move upward until you find the first ancestor larger than the current node.

Conceptually:

current
   ↑
ancestors
   ↓
first larger ancestor

This is one reason successor/predecessor are important BST interview concepts; the source lists both among the fundamental BST operations.

13. Predecessor

The predecessor is the largest key smaller than the current node.

The relationship is symmetric:

Successor
→ minimum of right subtree
→ otherwise first larger ancestor

Predecessor
→ maximum of left subtree
→ otherwise first smaller ancestor

14. Find the First Key Greater Than a Given Value

Suppose:

          10
        /    \
       5      15
      / \    /  \
     2   7  12  20

Find the smallest key greater than 11.

At 10:

10 < 11

So 10 cannot be the answer.

Move right.

At 15:

15 > 11

15 becomes a candidate.

Move left.

At 12:

12 > 11

Update the candidate.

Answer:

Python:

def first_greater(root, target):
    result = None
    current = root

    while current:
        if current.data > target:
            result = current
            current = current.left
        else:
            current = current.right

    return result

Invariant:

result = smallest value seen so far
         that is greater than target

Complexity:

Time: O(h)
Space: O(1)

15. Find the K Largest Elements

Because inorder traversal is ascending:

Left → Root → Right

reverse inorder is descending:

Right → Root → Left

Therefore:

def k_largest(root, k):
    result = []

    def reverse_inorder(node):
        if node is None or len(result) == k:
            return

        reverse_inorder(node.right)

        if len(result) < k:
            result.append(node.data)

        reverse_inorder(node.left)

    reverse_inorder(root)
    return result

The important optimization is:

Stop as soon as k elements have been collected.

Typical complexity:

O(h + k)

rather than traversing the entire tree.

16. Lowest Common Ancestor in a BST

Consider:

          20
        /    \
       10     30
      / \    / \
     5  15  25 35

Find the LCA of 5 and 15.

At 20:

5 < 20
15 < 20

Both lie in the left subtree.

At 10:

5 < 10
15 > 10

They split at 10.

Therefore:

LCA = 10

17. Python BST LCA

def lca_bst(root, a, b):
    current = root

    while current:
        if a < current.data and b < current.data:
            current = current.left

        elif a > current.data and b > current.data:
            current = current.right

        else:
            return current

    return None

Complexity:

Time: O(h)
Space: O(1)

Compare:

General binary tree
→ may need both subtrees

BST
→ ordering tells us where to go

This is a strong example of using the data structure’s invariant rather than treating the tree as a generic binary tree.

18. BST Range Queries

Suppose we need all keys in:

[10, 20]

At every node:

node < low
    ↓
left subtree cannot contain answer

node > high
    ↓
right subtree cannot contain answer

Otherwise, explore the relevant sides.

def range_query(root, low, high):
    result = []

    def dfs(node):
        if node is None:
            return

        if node.data > low:
            dfs(node.left)

        if low <= node.data <= high:
            result.append(node.data)

        if node.data < high:
            dfs(node.right)

    dfs(root)
    return result

The important idea is:

Use ordering to prune entire subtrees.

19. Delete From a BST

Deletion has three cases.

Case 1 — Leaf

   10
     \
      15

Delete 15.

Simply remove it.

Case 2 — One child

Delete 15.

Connect:

10 → 20

Case 3 — Two children

Delete 15.

Replace it with either:

inorder successor

or:

inorder predecessor

Then delete the replacement node from its original location.

20. Why the Successor Works

The successor of 15 is 20.

Because:

12 < 20

and 20 is the smallest value greater than 15, replacing 15 with 20 preserves the BST ordering.

The successor itself has no left child, so its removal becomes a simpler case.

This is the key structural reason successor-based deletion works.

21. Python BST Deletion

def delete_bst(root, key):
    if root is None:
        return None

    if key < root.data:
        root.left = delete_bst(root.left, key)

    elif key > root.data:
        root.right = delete_bst(root.right, key)

    else:
        if root.left is None:
            return root.right

        if root.right is None:
            return root.left

        successor = root.right
        while successor.left:
            successor = successor.left

        root.data = successor.data
        root.right = delete_bst(root.right, successor.data)

    return root

Complexity:

Time:  O(h)
Space: O(h)

for this recursive implementation.

22. Reconstruct a BST From Preorder

Suppose preorder is:

10, 5, 2, 7, 15, 12, 20

The first value is the root:

Values smaller than 10 belong to the left subtree.

Values greater than 10 belong to the right subtree.

A strong reconstruction technique maintains valid bounds.

def bst_from_preorder(preorder):
    index = 0

    def build(lower, upper):
        nonlocal index

        if index == len(preorder):
            return None

        value = preorder[index]

        if not (lower < value < upper):
            return None

        index += 1

        node = BinaryTreeNode(value)
        node.left = build(lower, value)
        node.right = build(value, upper)

        return node

    return build(float("-inf"), float("inf"))

The key idea is:

The valid range for a node is inherited from its ancestors.

23. Validation and Reconstruction Are the Same Pattern

This is an important connection.

Validation

Does every node satisfy
its inherited bounds?

Reconstruction

Create a node only when
it satisfies its inherited bounds.

Therefore:

BST bounds
   ↓
validation
+
reconstruction

The same invariant powers both.

24. Build a Balanced BST From a Sorted Array

Given:

[1, 2, 3, 4, 5, 6, 7]

choose the middle:

as root.

Then recursively use the middle of each half.

def sorted_array_to_bst(nums):
    def build(left, right):
        if left > right:
            return None

        mid = (left + right) // 2
        node = BinaryTreeNode(nums[mid])

        node.left = build(left, mid - 1)
        node.right = build(mid + 1, right)

        return node

    return build(0, len(nums) - 1)

Using index ranges avoids creating new slices at every recursive call.

25. Why Balance Matters

Balanced:

        8
      /   \
     4     12
    / \   / \
   2   6 10 14

has:

h = O(log n)

Skewed:

has:

h = O(n)

Therefore:

BST does not automatically mean O(log n).

The source explicitly emphasizes that logarithmic guarantees depend on the tree being height-balanced.

26. Balanced BST vs Ordinary BST

Operation	Balanced BST	Skewed BST
Search	`O(log n)`	`O(n)`
Insert	`O(log n)`	`O(n)`
Delete	`O(log n)`	`O(n)`
Min	`O(log n)`	`O(n)`
Max	`O(log n)`	`O(n)`
Successor	`O(log n)`	`O(n)`

The fundamental variable is:

height h

Most BST operations are:

O(h)

27. BST vs Hash Table

The source describes hash tables as providing expected O(1) lookup, while noting that they are not appropriate for order-related queries and require additional memory.

Requirement	Hash Table	BST
Exact lookup	Excellent	Good
Expected lookup	`O(1)`	`O(log n)` balanced
Ordered traversal	No	Yes
Min / Max	Not natural	Natural
Successor	Not natural	Natural
Predecessor	Not natural	Natural
Range queries	Poor fit	Good fit
Dynamic ordered data	Poor fit	Good fit

Staff-level question:

Do I need ordering semantics, or only membership lookup?

28. BST vs Sorted Array

Sorted array
→ fast binary search
→ excellent locality
→ expensive arbitrary insertion/deletion

BST
→ dynamic updates
→ ordered operations
→ pointer/node overhead
→ performance depends on balance

So ask:

read-heavy?
update-heavy?
range queries?
memory constraints?
static or dynamic?

29. BST and Binary Search

Part 11 taught:

Binary search
    ↓
check middle
    ↓
discard half

BST search does something conceptually similar:

check node
    ↓
discard left or right subtree

The difference is:

Sorted array
→ order encoded by positions

BST
→ order encoded by links

The underlying principle is the same:

Ordering
   ↓
Candidate elimination

30. BST and Sorting

Part 13 taught:

sort
 ↓
create order once

Part 14 teaches:

BST
 ↓
maintain order dynamically

Therefore:

Sorting
→ static ordering

BST
→ dynamic ordering

This is one of the most useful conceptual connections between the two parts.

31. BST and Heap

Do not confuse these structures.

BST

left < root < right

provides global ordering.

Heap

parent has priority over children

provides fast access to the minimum or maximum, but does not globally order all elements.

The source treats heaps and BSTs as separate structures with different use cases.

32. The BST Pruning Pattern

Many BST questions reduce to:

Can the answer exist
in the left subtree?

Can the answer exist
in the right subtree?

Ordering often lets us answer immediately.

target < node
    ↓
right subtree irrelevant

target > node
    ↓
left subtree irrelevant

This is the central algorithmic advantage of BSTs.

33. BST Problem-Solving Template

When you see a BST problem:

1. Identify the ordering invariant
2. Clarify duplicate policy
3. Determine what the target means
4. Decide whether one subtree can be eliminated
5. Maintain a candidate or bound
6. Traverse only relevant paths
7. State the invariant
8. Analyze complexity as O(h)
9. Convert h to O(log n) only if balanced
10. Discuss edge cases and scale

The source’s broader interview framework is:

Clarify
 ↓
Constraints
 ↓
Example
 ↓
Brute force
 ↓
Bottleneck
 ↓
Pattern
 ↓
Invariant
 ↓
Code
 ↓
Test
 ↓
Complexity
 ↓
Trade-offs

34. Common BST Mistakes

Mistake 1 — Assuming BST means O(log n)

Correct:

O(h)

and only:

O(log n)

when balanced.

Mistake 2 — Checking only immediate children

Use inherited bounds.

Mistake 3 — Ignoring duplicates

Define a duplicate policy.

Mistake 4 — Traversing the entire tree

Use pruning.

Mistake 5 — Forgetting recursion stack

Recursive BST algorithms can use:

O(h)

stack space.

35. Staff-Level Question: What If the Tree Becomes Skewed?

If the interviewer asks:

“What happens if the BST becomes skewed?”

Answer:

height → O(n)

and therefore:

search/insert/delete → O(n)

To preserve predictable logarithmic performance, use a self-balancing ordered tree such as an AVL or Red-Black tree.

The important architectural principle is:

Maintain a height bound so ordered operations remain efficient.

36. Staff-Level Question: BST or Database Index?

Suppose you need:

millions of records
range queries
frequent updates
persistence
concurrency

A simple in-memory BST is generally not the production answer.

You may instead use:

database indexes
B-trees / B+ trees
LSM-based structures
distributed indexing

The requirement remains:

maintain order
+
efficient search
+
efficient updates

The implementation changes because system constraints change.

37. BST Range Queries at Scale

For:

[low, high]

a BST can prune irrelevant branches.

           node
          /    \
       < low   > high
        ↓        ↓
      prune    prune

At production scale, storage engines commonly use more storage-efficient index structures than a naive pointer-based BST.

The algorithmic concept remains the same:

Use ordering to avoid work.

38. Complexity Habit for Staff Interviews

Never simply say:

O(log n)

Say:

“The operation is O(h). If the tree is height-balanced, h = O(log n); in the worst case, h = O(n).”

This demonstrates that you understand where the complexity comes from.

39. BST Pattern Map

                    BST
                     |
        +------------+------------+
        |            |            |
        v            v            v
      Search       Order        Update
        |            |            |
        v            v            v
    eliminate     min/max       insert
    subtree       successor     delete
                  predecessor
                     |
                     v
                  ranges

Core idea:

BST ordering
     ↓
Candidate elimination
     ↓
O(h) path
     ↓
O(log n) when balanced

40. Most Valuable BST Invariants

Invariant 1 — Ordering

left < node < right

Invariant 2 — Bounds

node must lie inside
the range imposed by ancestors

Invariant 3 — Search

target < node
→ target can only be in left subtree

Invariant 4 — Successor

smallest value greater than node

Invariant 5 — Predecessor

largest value smaller than node

Invariant 6 — Range pruning

node < low
→ left subtree irrelevant

node > high
→ right subtree irrelevant

41. BST Interview Cheat Sheet

Problem	Key Pattern	Complexity
Validate BST	Bounds / inorder	`O(n)`
Search	Ordering	`O(h)`
Insert	Search path	`O(h)`
Delete	Successor/predecessor	`O(h)`
Minimum	Go left	`O(h)`
Maximum	Go right	`O(h)`
Successor	Right-min / ancestor	`O(h)`
Predecessor	Left-max / ancestor	`O(h)`
First greater	Candidate + pruning	`O(h)`
K largest	Reverse inorder	`O(h + k)`
LCA	Ordering	`O(h)`
Range query	Pruning	`O(h + output)` approximately
Reconstruct preorder	Bounds	`O(n)`

Remember:

h = O(log n) only for a balanced BST
h = O(n) in the worst case

42. BST Decision Tree

Need exact lookup only?
        |
       YES
        ↓
   Hash table may be better

Need ordered lookup?
        |
       YES
        ↓
      BST

Need min/max repeatedly?
        |
       YES
        ↓
      BST / Heap

Need range queries?
        |
       YES
        ↓
    Ordered structure

Need top K only?
        |
       YES
        ↓
      Heap

Static sorted data?
        |
       YES
        ↓
 Sorted array + binary search

43. Part 13 → Part 14

The progression is:

Part 13 — Sorting
        ↓
Create order once
        ↓
Static ordering

Part 14 — BST
        ↓
Maintain order dynamically
        ↓
Search + insert + delete

Think of a BST as:

A dynamic ordered representation.

44. Part 11 → Part 13 → Part 14

There is an even deeper progression:

Part 11 — Searching
        ↓
Exploit existing structure

Part 13 — Sorting
        ↓
Create structure

Part 14 — BST
        ↓
Maintain structure

This is an excellent Staff-level mental model.

45. Final Staff-Level Mental Model

When you see a BST problem, don’t immediately write recursion.

Think:

What is the invariant?
        ↓
What ordering information do I have?
        ↓
Which subtree can I eliminate?
        ↓
What state/candidate must I maintain?
        ↓
Can I solve it iteratively?
        ↓
What is the height h?
        ↓
Is the tree balanced?
        ↓
What happens at scale?

The source emphasizes that Staff/Principal candidates should make their reasoning visible, connect patterns to constraints, explain correctness and complexity, and discuss trade-offs rather than merely producing working code.

46. Final Takeaway

The most important thing to remember about BSTs is not the insertion code.

It is this:

A BST stores ordering information in its structure, allowing us to eliminate entire subtrees from consideration.

Remember:

BST
 ↓
Ordering invariant
 ↓
Pruning
 ↓
O(h)
 ↓
O(log n) if balanced

Core operations:

Search
Insert
Delete
Min
Max
Successor
Predecessor
LCA
Range query
K largest
Validation
Reconstruction

The Staff-level lesson is:

Never claim O(log n) merely because something is a BST. First reason about the height, then establish whether the tree is balanced.

Part 14 in the Series

Part 10 — Heaps
↓
Part 11 — Searching
↓
Part 12 — Hash Tables
↓
Part 13 — Sorting
↓
Part 14 — Binary Search Trees

The progression is:

Heaps
  ↓
Prioritize

Searching
  ↓
Eliminate candidates

Hash Tables
  ↓
Fast membership

Sorting
  ↓
Create order

BST
  ↓
Maintain order dynamically

This sequence gives you a strong foundation for the more advanced algorithmic techniques that follow.