Tree Traversals

Definition

Generally a tree have 2 ways to traversal:

1. BFS - Breadth-First Search
2. DFS - Depth-First traversals

BFS 可以看作层序遍历，真菌在迷宫生长；DFS 则朝纵深遍历，如同闪电击中地面。

DFS

DFS - Depth-First traversals includes:

1. pre-order：顺时针访问节点，每次经过左侧访问
2. in-order：顺时针访问节点，每次 under node 访问
3. post-order：顺时针访问节点，每次经过右侧访问

pre、in、post 指 current node 何时被访问（print），左右子树访问顺序皆为 Left first

Pre-order Traversal

preOrder(BSTNode x) {
    if (x == null) return;
    print(x.key)
    preOrder(x.left)
    preOrder(x.right)
}

In-order Traversal

inOrder(BSTNode x) {
    if (x == null) return;    
    inOrder(x.left)
    print(x.key)
    inOrder(x.right)
}

Post-order Traversal

postOrder(BSTNode x) {
    if (x == null) return;    
    postOrder(x.left)
    postOrder(x.right)
    print(x.key)   
}

BFS

using Queue to track layers, Like:

public void BFS() {  
    Queue<Node<T>> queue = new Queue<>();  
    queue.enqueue(this);  
    BFS_helper(queue);  
}  
  
private void BFS_helper(Queue<Node<T>> queue) {  
    if (queue.isEmpty()) {  
        return;  
    }  
  
    Node<T> current = queue.dequeue();  
  
    if (current.left != null) {  
        queue.enqueue(current.left);  
    }  
  
    if (current.right != null) {  
        queue.enqueue(current.right);  
    }  
  
    System.out.print(current.value + " ");  
  
    BFS_helper(queue);  
}