← DSADSA 3.2
Binary Search Trees
Not started yet — 9 problems queued, the sorted-order specialization of Binary Trees.
Left subtree < node < right subtree; in-order traversal yields sorted output for free. Insert/delete/search are O(h) — O(log n) if balanced, O(n) worst case if not.
Sub-patterns
- A — Validate a BST. Confirm the ordering property actually holds.
- B — Insert / Delete. Maintaining the BST property under mutation.
- C — Kth-Smallest via In-Order. In-order traversal gives sorted order for free.
- D — BST Construction. Build a balanced BST from sorted input.
- E — Range / Successor Queries. Find the next/previous value or values within a range.
Practice set (9)
- Easy — Search in a Binary Search Tree, Convert Sorted Array to Binary Search Tree
- Medium — Validate Binary Search Tree, Kth Smallest Element in a BST, Insert into a Binary Search Tree, Delete Node in a BST, Lowest Common Ancestor of a BST, Binary Search Tree Iterator, Recover Binary Search Tree
Pending
Validate a BST
Confirm the left < node < right ordering property actually holds across the whole tree.
Pending
Insert / Delete
Maintain the BST property under mutation.
Pending
Kth-Smallest via In-Order
In-order traversal yields sorted output for free — the kth value falls out of the kth visit.
Pending
BST Construction
Build a balanced BST from sorted input.
Pending
Range / Successor Queries
Find the next/previous value, or all values within a range.
Notes from readers
Comments — via GitHub