Basic Tree Operations

Start by asking whether the structure is a general binary tree, a binary search tree, or a balanced tree, because operations differ. For traversal, preorder processes node then children, inorder visits left then node then right, postorder processes children before node, and level order uses a queue. A recursive DFS must return immediately on null; an iterative DFS should make push order deliberate so pop order matches the traversal. For a BST lookup, compare the target and descend one branch, but do not use that rule on a general tree. Discuss degenerate trees: recursion depth can reach n, so an explicit stack has the same O(h) auxiliary space where h is height. Every traversal visits each node once, giving O(n) time; BFS queue space is O(w), where w is maximum width. Test an empty tree, one node, skewed tree, and duplicate-key policy if it is a BST.