BST Basics 10 XP Easy

Ctrl+Enter Run Ctrl+S Save

A Binary Search Tree (BST) is a binary tree with one special rule: for every node, ALL left descendants are smaller and ALL right descendants are larger. 🌲

💡 Think of it like this: Imagine organizing books on a shelf. Pick any book — everything to its LEFT has a title that comes BEFORE it alphabetically, and everything to its RIGHT comes AFTER. That's a BST!

#       8         ← root
#      / \
#     3   10      ← 3 < 8 < 10 ✓
#    / \    \
#   1   6    14   ← 1 < 3, 6 > 3, 14 > 10 ✓
#      / \
#     4   7       ← 4 < 6. 7 > 6 ✓

BST Operations:

🔍 Search: Compare with node → go left (smaller) or right (larger) → O(log n) average
➕ Insert: Search for position → add as leaf → O(log n) average
➖ Delete: Three cases (leaf, one child, two children) → O(log n)
📋 In-order traversal: Left → Node → Right gives sorted order!

💭 Go for it! Apply the approach above in your own code. If you get stuck, use the hint below! 🔥

⚠️ Worst case: If you insert sorted data (1, 2, 3, 4, 5...), the BST becomes a linked list and operations become O(n). This is why balanced BSTs (AVL, Red-Black) exist!

📋 Instructions

Build a BST and print its inorder traversal (should be sorted). Also implement a simple search function.

Build the tree manually with TreeNode. Inorder traversal of BST gives sorted output. Search: if val < node.val, go left. If val > node.val, go right. If equal, found!

⚠️ Try solving it yourself first — you'll learn more!

# In-order traversal of BST above:
# 1, 3, 4, 6, 7, 8, 10, 14 ← SORTED!

def inorder(node):
    if not node:
        return
    inorder(node.left)   # Visit left
    print(node.val)      # Visit node
    inorder(node.right)  # Visit right

🧪 Test Cases

Input

inorder(root)

Expected

[1, 3, 4, 6, 7, 8, 10, 14]

Test case 1

Input

search_bst(root, 6)

Expected

True

Boolean check

Input

search_bst(root, 5)

Expected

False

Boolean check

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›