DSA · Theory

Searching in BST

Theory

89/810

Searching in BST

Searching in BST is a DSA topic. In plain words you use it for folder on disk in a file explorer. Don’t start with a slogan — start with that picture.

Smallest example: left < root < right. Type it, run it, and say what you see. If you can do that from memory, you know Searching in BST.

From the example next to this theory: Searching in BST — bST invariant: left < node < right — enables log-time search when balanced.

Trap — unbalanced BST becoming a list. Fix that before you talk about advanced DSA.

Viva — what is Searching in BST? Then show left < root < right. Then name the trap.

Diagram

Exam tip

What is Searching in BST? Show this: left < root < right. Trap: unbalanced BST becoming a list.

Example

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root

root = None
for v in [5, 2, 7, 1]:
    root = insert(root, v)
print(root.val, root.left.val, root.right.val)

Searching in BST — bST invariant: left < node < right — enables log-time search when balanced.

Short notes

DefSearching in BST — folder on disk in a file explorer.
Ruleleft < root < right
Trapunbalanced BST becoming a list
Usea file explorer

class Node: def __init__(self, val): self.val = val self.left = None self.right = None def insert(root, val): if root is None: return Node(val) if val < root.val: root.left = insert(root.left, val) elif val > root.val: root.right = insert(root.right, val) return root root = None for v in [5, 2, 7, 1]: root = insert(root, v) print(root.val, root.left.val, root.right.val)

Searching in BST

Example

Short notes

Questions

Searching in BST

Example

Short notes

Questions