Searching without sorted order
In a general binary tree, unlike a binary search tree, values can be in any position. It is like looking for a person in an office building with no directory: you may have to check every room.
So to find the target you must be ready to look through every node, in both the left and the right subtree.
Unsorted: the target could be in the left subtree or the right one.
Base case: an empty spot cannot hold the target: answer no.
root = [1, 2, 3, null, 4], target = 4
No sorted order here, so 4 could be anywhere. Is the root 4? No, it's 1.
Move 1 of 4
Three ways to find a match
A match can be in one of three places: at the current node itself, somewhere in the left subtree, or somewhere in the right subtree.
If the current node matches, answer yes straight away, since there is no need to look further. Otherwise ask both subtrees, and say yes if either one says yes. That is an OR of the two answers.
Early exit: a match at this node means yes, without checking the children.
Left or right: yes if either side contains the target.
if not root:
return False
if root.val == target:
return True
if search_tree(root.left, target):
return True
return search_tree(root.right, target)