Core idea
A tree is for hierarchy. A BST is for ordered data where left is smaller and right is larger.
In interviews, first say what structure fits the shape of the data. Then say the cost for search, insert, delete, and traversal.
When trees fit
Use trees for folders, comments and replies, organisation charts, DOM-like UI, tournament brackets, and decision paths.
A binary tree node has up to two children. A general tree can have many children. A BST is a binary tree with an ordering rule.
BST costs
A balanced BST gives search, insert, and delete in O(log n). An inorder traversal gives sorted order in O(n).
A bad BST can become a linked list if values are inserted in sorted order. Then search becomes O(n). In interviews, mention this risk.
Common mistake
Do not use a BST only because the word “tree” appears in the problem. If you only need parent-child traversal, a normal tree is enough.
Do not promise O(log n) for every BST. Say “balanced BST” when you mean O(log n).
BST search code
Add this small Python file to your kit. Keep it boring and testable.
It shows the rule clearly: go left for smaller values, right for larger values.
# trees/bst_search.py
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def search(root, target):
cur = root
while cur:
if cur.val == target:
return True
if target < cur.val:
cur = cur.left
else:
cur = cur.right
return False
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)Test the rule
Your repo should prove code works. Add one test for search and one for sorted inorder traversal.
If you use pytest, this can go in tests/test_bst_search.py.
from trees.bst_search import Node, search, inorder
def sample_tree():
return Node(
8,
Node(3, Node(1), Node(6)),
Node(10, None, Node(14))
)
def test_search_finds_existing_value():
assert search(sample_tree(), 6) is True
def test_search_rejects_missing_value():
assert search(sample_tree(), 7) is False
def test_inorder_is_sorted_for_bst():
assert inorder(sample_tree()) == [1, 3, 6, 8, 10, 14]Interview phrasing
Use a short line like this in your notes: “I chose a BST because I need ordered search and sorted traversal. If the tree is balanced, search is O(log n); worst case is O(n).”
This is enough for most internship interviews. Then move to code.
Do this now
Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.
0 of 5 done