Node in subtree or not

Summary

Find whether a given node is present in the subtree rooted at another node. This problem involves tree traversal and manipulation, requiring an understanding of recursive algorithms.

Detailed Explanation

Given a binary tree with nodes having values, we need to write an algorithm that checks if a specific node x exists in the subtree rooted at node y. The algorithm should return a boolean value indicating whether x is present in the subtree or not.

To solve this problem, we can use a recursive approach. We start by checking if y is equal to x. If they are the same, then x exists in the subtree rooted at y, and we return true.

If y is not equal to x, we recursively traverse the left and right subtrees of y and check if x exists in either of them. This process continues until we find x or reach a leaf node.

Here's the step-by-step breakdown:

1. If y is null, return false (since x cannot exist in an empty subtree).
2. Check if y is equal to x. If true, return true.
3. Recursively traverse the left subtree of y and check if x exists there.
4. If not, recursively traverse the right subtree of y and check if x exists there.
5. If x is found in either the left or right subtree, return true. Otherwise, return false.

Time complexity: O(n), where n is the number of nodes in the subtree rooted at y. Space complexity: O(h), where h is the height of the tree (since we use recursive function calls).

Optimized Solutions

Java