Return true if a target value appears anywhere in the binary tree.
treeIncludes(root, target)
Input format: tree | target — level-order tree with x for missing children,
a pipe, then the target.
(3 9 20 x x 15 7), 15 // → true
(3 9 20 x x 15 7), 42 // → false
(empty), 1 // → false
This tree has no ordering guarantee — it's not assumed to be a binary search tree, so there's no shortcut like "go left if the target is smaller." Without that structure, the only sound approach is to check every node until you find the target or run out of tree.
For any node, the target is present in this subtree if one of three things holds: this node itself holds the target, or it's in the left subtree, or it's in the right subtree. That's "search everywhere" translated into a yes/no question each node answers using its own value and two smaller yes/no answers from its children.
An empty subtree can't contain anything, so it always answers "not found." This stops every branch of the recursion once you run off the bottom into an empty spot.
Checking the current node before recursing means you can stop the moment you find a match. Combined with short-circuiting "or," once you find the target anywhere, none of the remaining subtrees get visited. Best case (target near the root) is fast; worst case (target missing, or last node checked) still visits every node once.
Either order would find the target eventually. Recursion gives you depth-first for free, and there's no need here for level-based order, shallowest-occurrence info, or a reconstructed path — so there's no reason to pay for the queue BFS requires. When a problem doesn't ask for shortest distance or level info, DFS is the simpler default.
Worst case touches every node once, so time is proportional to the number of nodes; memory is bounded by the tree's height from the call stack.
def tree_includes(root, target):
if root is None:
return False
if root.val == target:
return True
return tree_includes(root.left, target) or tree_includes(root.right, target)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.