What tree traversal methods can you name and how do they work?

The main methods of tree traversal are:

1. Depth-First Search (DFS):

   • Pre-order: visit the root first, then recursively the left subtree, then the right.
   • In-order: visit the left subtree first, then the root, then the right subtree. Often used for binary search trees to get sorted order.
   • Post-order: visit the left subtree first, then the right, then the root.

2. Breadth-First Search (BFS):

   • Visit nodes level by level, starting from the root, then all nodes of the first level, then the second, and so on. Usually implemented with a queue.

Example of depth-first traversal (pre-order) in Java:

void preOrder(Node node) {
    if (node == null) return;
    System.out.println(node.value);
    preOrder(node.left);
    preOrder(node.right);
}