Trees, BSTs, and Traversal

A binary tree links each node to up to two children, and a binary search tree adds the invariant that everything left is smaller and everything right is larger, which gives O(log n) search on a balanced tree. The traversal skills interviews test are the three depth-first orders (pre, in, post), breadth-first level order, and switching between recursion and an explicit stack. Applied-AI interviews probe this because in-order traversal of a BST yields sorted output, and the recursion-to-stack conversion is the same skill behind iterative DFS everywhere.