Algorithms | Traverse Binary Tree

In this article we will talk about Traverse Binary Tree.

Here is an example of traversing trees with inorder, preorder, postorder 

1
2
3
4
5
6
7
8
9
public class Node {
    int val;
    public Node left;
    public Node right;
    Node(int val) {
        this.val = val;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void visit(Node node) {
    System.out.format("%s ->", node.val);
}
public static void inorder(Node node) {
    if (node == null) return;
    inorder(node.left);
    visit(node);
    inorder(node.right);
}
public static void preorder(Node node) {
    visit(node);
    preorder(node.left);
    preorder(node.right);
}
public static void postorder(Node node) {
    if (node == null) return;
    preorder(node.left);
    preorder(node.right);
    visit(node);
}

Moreover you can BFS and DFS on trees.

BFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bfs(Node root) {
    if (root == null) return;
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
        int size = queue.size();
        for (int j = 0; j < size; ++j) {
            Node node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            visit(node);
        }
    }
}

DFS: 

1
2
3
4
5
6
7
8
9
10
11
public static void dfs(Node root) {
    if (root == null) return;
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
        Node node = stack.pop();
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
        visit(node);
    }
}