Trees, BSTs, and Traversal

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