Tree DFS: Depth-First Search, a Traversal Method from Root to Leaf

A tree consists of nodes and edges, where each node (except the root) has exactly one parent and can have multiple children. Depth-First Search (DFS) is a traversal method that "goes deep into one path until it ends, then backtracks." Tree DFS traversals include pre-order (root → left → right), in-order, and post-order, with pre-order most directly reflecting root-to-leaf paths. For recursive pre-order traversal: visit the current node → recursively traverse the left subtree → recursively traverse the right subtree. Using the example tree (root 1, left child 2, right child 3; 2 has left child 4 and right child 5), the traversal order is 1 → 2 → 4 → 5 → 3. For non-recursive implementation, a stack is used: initialize with the root, then repeatedly pop the top node, visit it, and push its right child first followed by its left child onto the stack. Root-to-leaf DFS traversal is applied to problems like path sum calculation and path output. Recursive implementation is intuitive, while non-recursive stack-based methods are suitable for large datasets. Mastering pre-order traversal is a core skill for tree structure manipulation.