Binary Tree(2)

BFS vs DFS for Binary Tree

What are BFS and DFS for Binary Tree?

A Tree is typically traversed in two ways:

• Breadth First Traversal(Or Level Order Traversal)
• Depth First Traversals
  • Inorder Traversal(Left-Root-Right)
  • Preorder Traversal(Root-Left_Right)
  • Postorder Traversal(Left-Right-Root)

image.png

BFS and DFS of above Tree
Breadth First Trvaversals: 1 2 3 4 5
Depth First Traversals:
    Preorder Traversal :  1 2 4 5 3
    Inorder Traversal  : 4 2 5 1 3
    Postor Traversal : 4 5 2 3 1

The most important points is, BFS starts visiting nodes from root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.

Tree Traversals (Inorder, Preorder and Postorder)

#include<stdio.h>
#include<stdlib.h>

typedef int DataType;
typedef struct node
{
    DataType data;
    struct node * left;
    struct node * right;
} Node;

Node * newNode(DataType data)
{
    Node * temp = (Node*)malloc(sizeof(Node));
    if (temp == NULL)
    {
        puts("Memory allocation failed.");
        exit(1);
    }
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;

}

void printPostorder(Node * node)
{
    if (node == NULL)
        return;
    printPostorder(node->left);
    printPostorder(node->right);
    printf("%d ",node->data);

}

void printInorder(Node * node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    printf("%d ",node->data);
    printInorder(node->right);

}

void printPreorder(Node * node)
{
    if(node == NULL)
        return;
    printf("%d ",node->data);
    printPreorder(node->left);
    printPreorder(node->right);

}

int main(void)
{
    Node * root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("\nPreorder traversal of binary tree is \n");
    printPreorder(root);

    printf("\nInorder traversal of binary tree is \n");
    printInorder(root);

    printf("\nPostorder traversal of binary tree is \n");
    printPostorder(root);

    return 0;
}