CODEWITHSUNDEEP
algorithmrecursionbinary-search-treedepth-first-search
Kiran B.R
Kiran B.R

Reputation: 21

Is pre-order traversal a depth-first method?

Is pre-order traversal a depth-first algorithm? I'm using it in my search below.I have included the code below.

public bool DFS1(int value, BSTNode root)
{    // Pre-order search

    if (root == null)
        return false;

    if (root.data == value)
    {
        Console.WriteLine("found");
        return true;
    }

    DFS1(value, root.left); //vist the left node
    return DFS1(value, root.right); // vist the right node.
}

Upvotes: 2

Views: 357

Answers (1)

Prune
Prune

Reputation: 77847

Yes, it is depth-first: you will complete the left sub-tree completely before you look at the original root's right node. However, you need to consider the result from that left search. At the moment, this will return true iff the rightmost node has the target value.

return DFS1(value, root.left) or
       DFS1(value, root.right)

Most compilers will optimize this (short-circuit), so that if the left side returns true, the right will not execute. If not, you can write it yourself:

if (DFS1(value, root.left))
    return true;
else
    return DFS1(value, root.right);

Upvotes: 3

Related Questions