What is depth-first tree traversal (DFS)?

Depth-first traversal (DFS, Depth-First Search) is a way of traversing a tree in which the algorithm goes deep along a branch until it reaches the end (a leaf), and only then backtracks to walk the other branches.

---

#Principle

1. Start at the root.
2. Follow the first available child all the way down.
3. When you can't go any further, backtrack to the previous node.
4. Continue until every node has been visited.
5. It is usually implemented with a stack (LIFO), either explicitly or via recursion.

---

#Example

Possible traversal types (DFS variants):

• Pre-order: A, B, D, E, C
• In-order: D, B, E, A, C
• Post-order: D, E, B, C, A

---

#Features of DFS

• Uses a stack or recursion.
• Good for tasks where you need to explore the whole structure or find a path down to depth.
• Can be faster than BFS if the target element is deep in the tree.

---

#Summary

DFS is a traversal that goes deep along branches, exploring each branch fully before moving on to the next one. It is implemented with a stack or recursion and has three main traversal orders: pre-, in-, post-order.