Trees and binary search trees

Trees represent hierarchy through parent-child edges. Binary trees constrain each node to left and right children; binary search trees add an ordering invariant. Traversal order matters: preorder is useful for serialization, inorder exposes sorted BST values, and postorder helps delete or aggregate children first.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Interviewers expect you to name base cases, explain recursion depth, and distinguish a general binary tree from a balanced search tree.

Common pitfalls: A skewed BST is a linked list with O(n) operations. Do not validate a BST by checking only immediate children; carry min and max bounds through recursion.

Checklist:

• Choose traversal order.
• Track depth and stack space.
• Carry BST bounds.
• Handle null children.