Binary Trees - Depth First Traversal and Search

Binary Tree - Depth First Traversal (DFT)

• Depth First Traversal starts at the root (or an arbitrary node for a graph) and explores as far as possible before back-tracking.
• There are generally 3 different algorithms - pre-order traversal, in-order traversal, post-order traversal

Applications

• In-order traversal of a BST (binary search tree) results in a sorted traversal.
• When searching for a particular node, use pre-order traversal as it will visit the nodes prior to traversing its children.
• If you want to process the children of a node prior to the parents, use post order traversal.

Pre-Order Traversal

• Visit, preorder(left), preorder(right)
• The algorithm to use for DFS (Depth First Search)

Algorithm

//
// depth first pre-order
//
void preorder (Node* head)
{
    if (!head)
        return;

    // e.g. visit
    std::cout << head << " ";

    preorder (head->left);
    preorder (head->right);
}

In-Order Traversal

• Inorder(left), visit, inorder(right)

Algorithm

//
// depth first in-order
//
void inorder (Node* head)
{
    if (!head)
        return;

    inorder (head->left);

    // e.g. visit
    std::cout << head << " ";

    inorder (head->right);
}

Post-Order Traversal

• Postorder(left), postorder(right), visit

Algorithm

//
// depth first post-order
//
void postorder (Node* head)
{
    if (!head)
        return;

    postorder (head->left);
    postorder (head->right);

    // e.g. visit
    std::cout << head << " ";
}

Binary Tree - Depth First Search (DFS)

Algorithm

void dfs (Node* n, int end, std::vector<Node*>& path=std::vector<Node*>())
{
    if (!n)
        return;

    path.push_back(n);

    if (n->value == end)
    {
        print_path(path);
        return;
    }

    if (n->left)
        dfs(n->left, end, path);

    if (n->right)
        dfs(n-gt;right, end, path);
   
    path.pop_back();
}