How to implement tree traversal and search algorithms in Java?

In Java, tree traversal and search algorithms can be implemented using recursion or iteration. There are three common ways to traverse a tree: pre-order traversal, middle order traversal, and post-order traversal. The tree search algorithm includes breadth-first search (BFS) and depth-first search (DFS). The implementation of these algorithms is described in detail below.

1 Tree traversal algorithm:

1.1 Pre-order traversal:

• The pre-order traversal first accesses the root node, then recursively traverses the left subtree, and finally recursively traverses the right subtree.
• Code example:

public void preOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.print(root.val + " "); // 访问根节点
    preOrderTraversal(root.left); // 遍历左子树
    preOrderTraversal(root.right); // 遍历右子树
}           

1.2 Intermediate traversal:

• Middle-order traversal first recursively traverses the left subtree, then accesses the root node, and finally recursively traverses the right subtree.
• Code example:

public void inOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrderTraversal(root.left); // 遍历左子树
    System.out.print(root.val + " "); // 访问根节点
    inOrderTraversal(root.right); // 遍历右子树
}           

1.3 Post-order traversal:

• Post-order traversal first recursively traverses the left subtree, then recursively traverses the right subtree, and finally accesses the root node.
• Code example:

public void postOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    postOrderTraversal(root.left); // 遍历左子树
    postOrderTraversal(root.right); // 遍历右子树
    System.out.print(root.val + " "); // 访问根节点
}           

2 Tree search algorithm:

2.1 Breadth-First Search (BFS):

• Breadth-first search is implemented by using queues that enqueue the root node first, and then loop through the queue: queue a node, access the node, and enqueue all its child nodes.
• Code example:

public boolean breadthFirstSearch(TreeNode root, int target) {
    if (root == null) {
        return false;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.val == target) {
            return true;
        }
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    return false;
}           

2.2 Deep First Search (DFS):

• Depth-first search is implemented by using the stack, first putting the root node on the stack, and then looping through the stack: one node is stacked, the node is accessed, and all its child nodes are added to the stack.
• Code example 1 (recursive implementation):

public boolean depthFirstSearchRecursive(TreeNode root, int target) {
    if (root == null) {
        return false;
    }
    if (root.val == target) {
        return true;
    }
    return depthFirstSearchRecursive(root.left, target) || depthFirstSearchRecursive(root.right, target);
}           

• Code example 2 (iterative implementation):

public boolean depthFirstSearchIterative(TreeNode root, int target) {
    if (root == null) {
        return false;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node.val == target) {
            return true;
        }
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    return false;
}           

Note: In the preceding code example, assume that the nodes of the tree are defined as follows:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
       this.val = val;
    }
}
           

This is how tree traversal and search algorithms are implemented in Java. Both the traversal algorithm and the search algorithm can be implemented using recursion or iteration. For the depth-first search algorithm, you can choose recursive implementation or iterative implementation according to the actual situation; The breadth-first search algorithm is generally implemented in an iterative manner, using queues as auxiliary data structures. According to the specific requirements and the structure of the tree, the appropriate algorithm can be selected to apply to the actual scenario.