# Binary Tree Traversal
> Binary Tree $\rightarrow$ [Data Structure (II) - 01 Tree](/ijB4_IbKQsqFHa47-OTK6Q#Binary-Tree)
* Tree traversal: process of visiting each node in the tree exactly **once** in some order.
* visit: Reading or processing data in a node
# depth-first
Using recursion again. In the flowcharts below
* root( D ) means to read or process the data of root
* left( L ) means to vist the left subtree
* right( R ) means to vist the right subtree
## Preorder(DLR)

flowchart LR
root-->left-->right

## Inorder(LDR)
actual I use it when teaching print BST in the [Data Structure (II) - 01a Binary Search Tree](/CE4kP7jeT5GE7bb-zePLCA)

flowchart LR
left-->root-->right

## Postorder(LRD)

flowchart LR
left-->right-->root

## Implementaion

void preorder(Node* root){
    if(root!=NULL){
    	cout<< root->data << " ";//D
    	preorder(root->left);//L
    	preorder(root->right);//R
    }
}
void inorder(Node* root){
    if(root!=NULL){
    	inorder(root->left);//L
    	cout<< root->data << " ";//D
    	inorder(root->right);//R
    }
}
void postorder(Node* root){
    if(root!=NULL){
    	postorder(root->left);//L
    	postorder(root->right);//R
    	cout<< root->data << " ";//D
    }
}

# breadth-first

We will use the tree below as example:

flowchart
F-->D
F-->J
D-->B
D-->E
B-->A
J-->G
J-->K
G-->I
I-->H

## Level Order
At the beginning, we go tho first level (`L0`), visit every nodes in the level then we go to next level.

flowchart LR
F-->D-->J-->B-->E-->G-->K-->A-->I-->H
f(L0)-->d(L1)-->j(L1)-->b(L2)-->e(L2)-->g(L2)-->k(L2)-->a(L3)-->ia(L3)-->ha(L3)

But how do we vist `J` after visit `D`? There isn't any link between them. We can use queue to storage the nodes we should visit.
1. enqueue the root
2. do the process
3. **enqueue the children**
4. pop the root (the front)
5. visit the new front and go to the process 2

flowchart LR
l0(Queue)-->F
l1(Queue)-->D-->J
l2(Queue)-->B-->E-->G-->K
l3(Queue)-->A-->I-->H

#include<queue>

void levelOrder(Node* root){
    if(root!=NULL){
        queue<Node*> nodes;
        nodes.push(root);
        while(!nodes.empty()){
            if(nodes.front()!=NULL){
            	cout<<nodes.front()->data<<" ";
            	if(nodes.front()->left!=NULL){
            	    nodes.push(nodes.front()->left);
            	}
            	if(nodes.front()->right!=NULL){
            	    nodes.push(nodes.front()->right);
                }
                nodes.pop();
            }
        }
    }
}