Depth first Search and Breadth First Search (golang)

Note: Code to generate binary tree from these numbers can be found at https://medium.com/@houzier.saurav/binarytree-golang-cb956afb9693

BFS(Breadth first search) is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the tree layerwise thus exploring the neighbor nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbor nodes.

//BFS to print the tree in breadth first fashion
type Tree struct {
    Value  int
    Left   *Tree
    Right  *Tree
    Repeat int
    Parent *Tree
}
func BFS(tree *Tree) []int {
    queue := []*Tree{}
    queue = append(queue, tree)
    result := []int{} 
    return BFSUtil(queue, result)
}
func BFSUtil(queue []*Tree, res []int) []int {
//This appends the value of the root of subtree or tree to the 
//result
    if len(queue) == 0 {
        return res
     }
    res = append(res, queue[0].Value)
    if queue[0].Right != nil {
        queue = append(queue, queue[0].Right)
    }
    if queue[0].Left != nil {
        queue = append(queue, queue[0].Left)
    }
    return BFSUtil(queue[1:], res)
   }
53 5776 23 6555 170 45 19 223 75 49 29 21 3 802 90 63 34 24 2 887 456

Inorder traversal

1. First, visit all the nodes in the left subtree
2. Then the root node
3. Visit all the nodes in the right subtree

inorder(root->left)
display(root->data)
inorder(root->right)
2 3 19 21 23 24 29 34 45 49 53 63 75 90 170 223 456 802 887 5776 6555

Preorder traversal

1. Visit root node
2. Visit all the nodes in the left subtree
3. Visit all the nodes in the right subtree

display(root->data)
preorder(root->left)
preorder(root->right)
53 23 19 3 2 21 45 29 24 34 49 5776 170 75 63 90 223 802 456 887 6555

Postorder traversal

1. visit all the nodes in the left subtree
2. visit the root node
3. visit all the nodes in the right subtree

postorder(root->left)
postorder(root->right)
display(root->data)
2 3 21 19 24 34 29 49 45 23 63 90 75 456 887 802 223 170 6555 5776 53

When to use Pre-Order, In-order or Post-Order?

The traversal strategy the programmer selects depends on the specific needs of the algorithm being designed. The goal is speed, so pick the strategy that brings you the nodes you require the fastest.

1. If you know you need to explore the roots before inspecting any leaves, you pick pre-order because you will encounter all the roots before all of the leaves.
2. If you know you need to explore all the leaves before any nodes, you select post-order because you don’t waste any time inspecting roots in search for leaves.
3. If you know that the tree has an inherent sequence in the nodes, and you want to flatten the tree back into its original sequence, than an in-order traversal should be used. The tree would be flattened in the same way it was created. A pre-order or post-order traversal might not unwind the tree back into the sequence which was used to create it.

Feel free to email me at graphicaldot@zoho.com.