Recursively searching binary tree issue

Question

I have written the below code for recursively searching binary tree . Even though my system.out statement is getting executed , the return statement is not returning out of entire recursion and thus this method not returning true.

Can anyone suggest how can I return out of entire recursion.?

public static boolean isElementinTree(int num, BinaryTreeNode root) { if (root != null) { int rootVal = root.getData(); BinaryTreeNode left = root.getLeft(); BinaryTreeNode right = root.getRight(); if (left != null) { isElementinTree(num,left); } if (right != null) { isElementinTree(num,right); } if (num == rootVal) { System.out.println("------ MATCH -----"); return true; } } return false; }

I think you should first check if the data in the node matches and only if it doesn't, you should move to the left or to the right subtree. — Radu Murzea
– Radu Murzea, Commented Aug 7, 2012 at 13:52

Jon Skeet · Accepted Answer · 2012-08-07 13:52:01Z

This is the problem:

if (left != null) { isElementinTree(num,left); } if (right != null) { isElementinTree(num,right); }

You're calling the method in those cases - but ignoring the result. I suspect you just want to change each of those to return immediately if it's found:

if (left != null && isElementinTree(num, left)) { return true; } if (right != null && isElementinTree(num, right)) { return true; }

Or to make the whole thing more declarative, you can do it more simply:

public static boolean isElementinTree(int num, BinaryTreeNode root) { return root != null && (root.getData() == num || isElementInTree(num, root.getLeft()) || isElementInTree(num, root.getRight())); }

It's fine to call isElementInTree with a null second argument, as you're already protecting against that with the first part.

that would never return true for elements in the right half of the tree
That would only search the first branch, or am I missing something?
@pcalcao: See my second edit. The whole body collapsed to three lines :)
Nice, you have my upvote. Concise and doesn't sacrifice too much readability.
I'd say the three line version is more readable as it captures the essence of the algorithm precisely - the value you are looking for is in the tree if it matches the root node, or is in the left subtree, or is in the right subtree.

Husmus · Accepted Answer · 2018-12-18 13:09:24Z

What is wrong with a simple solution like this:

public static boolean isElementinTree(int num, BinaryTreeNode root) { return root != null && //The tree is non-null (num == root.getData() || //We have num in this node OR isElementInTree(num, root.getLeft()) || //We have num in left subtree OR isElementInTree(num, root.getRight()) ); //We have num in right subtree }

pcalcao · Accepted Answer · 2012-08-07 13:52:02Z

You need to check if the value is in one of the branches, and save that result.

Initialize a variable boolean found = false;.

When you do the recursive call, you need to do something like:

found = isElementinTree(num,left)

same thing for the right side.

At the end, instead of returning false, check if the value was found on a branch, simply return found;

Also, first check if the number you are looking for isn't on the Node itself, instead of searching each branch first. Simply switch the order of the if's.

Ian Roberts · Accepted Answer · 2012-08-07 13:58:51Z

If you do find the element you're looking for in the left or right subtrees you need to return this fact back up to the caller:

 if (left != null) { if(isElementinTree(num,left)) return true; } if (right != null) { if(isElementinTree(num,right)) return true; }

Only if you find it in none of the left tree, right tree and current node do you eventually fall through to the final return false.

Maher Rezeq · Accepted Answer · 2013-08-01 00:57:52Z

Recursion solution:

boolean isElementinTree (int num, BinaryTreeNode root) { if(root == null) return false; if(root.value == num) return true; boolean n1 = isElementinTree(num,root.getLeft()); boolean n2 = isElementinTree(num,root.getRight()); return n1 ? n1 : n2; }

Collectives™ on Stack Overflow

Recursively searching binary tree issue

5 Answers 5

6 Comments

Comments

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

6 Comments

Comments

Comments

Comments

Comments

Related