1
boolean dfs(TreeNode root, int target) {
        if (root == null)
            return false;
        if (root.data == target)
            return true;
        return dfs(root.left, target) || dfs(root.right, target);
    }

What is the program actually doing in the last line...can anyone please explain.?

Ravi Bhatt
  • 3,147
  • 19
  • 21
A15
  • 2,345
  • 2
  • 15
  • 7
  • Funny how most people completely miss fact that right sub-tree is never explored if `target` is found in left sub-tree due to `||` short circuiting. – RokL Jan 31 '12 at 10:27
  • @UMad that is true but it is also the desired behaviour. If you find `target` in the left sub-tree, then you don't need to explore the right sub-tree. So that `||` short-circuit is in fact good. – Radu Murzea Jan 31 '12 at 10:37
  • I know it's desired and intentional. I was commenting on explanations which most often state that both subtrees are explored, without mentioning that exploration of right subtree is conditional. – RokL Jan 31 '12 at 11:33

5 Answers5

2

It is recursively exploring left branch looking for target and then right branch for target.

To be more specific the algorithm does this:

  • if target is found in this node, return true
  • else, recurse into left subtree looking for target
  • if target is in left subtree then recursive call will return true and short-circuit on || will make the method return immediately
  • else the second sub-expression in || expression is evaluated, recursing into right subtree looking for target, returns boolean signifying presence of target in right subtree
RokL
  • 2,663
  • 3
  • 22
  • 26
0

The last line

return dfs(root.left, target) || dfs(root.right, target);

is equivalent to

if (dfs(root.left, target)) {
   return true;
}
return dfs(root.right, target);

In other words, the method is applied recursively to the left subtree. Only if that returns false, the method is also recursively applied to the right subtree.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
0

The program applies the same method (dfs) to the left and right branches of the tree and returns the "OR" of both results.

Basically if the target isn't found in the current node, then check if it can be found in the left branch OR the right branch. This is applied recursively until there are no nodes left (when it matches the first case of root being null).

You can check out my answer here: Recursion - trying to understand and see if it helps understanding the problem.

Community
  • 1
  • 1
pcalcao
  • 15,789
  • 1
  • 44
  • 64
0

It's doing a recursive call to explore first the left, then the right subtree.

It means it will first go down on the left until it gets to a leaf, then backtrack and go down on the right.

It returns true if it finds target in the left OR in the right subtree.

http://en.wikipedia.org/wiki/Depth-first_search

Savino Sguera
  • 3,522
  • 21
  • 20
0

It's a recursive call where dfs first traverse all nodes left to root and then all nodes right to root and 'OR' the result of these two calls to return either true or false.

Waqas
  • 6,812
  • 2
  • 33
  • 50