Search a binary tree
Check the root value, and if it doesn't match, check either the left or right subtree. About 8 minutes.
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.
No sorted order here, so 4 could be anywhere. Is the root 4? No, it's 1.
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.
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)If target is found in root.left, does search_tree(root.right, target) need to run?
- ANo, the boolean OR short-circuits
- BYes, both sides must always finish
Show the answer
No, the boolean OR short-circuits. Because true || anything is true, once the left side returns true, the right call is skipped.
Search a binary tree
Given the root of a binary tree and an integer target, return true if target exists anywhere in the tree, and false otherwise.
root = [1, 2, 3, null, 4], target = 4 → true
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val, target ≤ 1,000,000