427. Find a Value in a BST

Given a binary search tree and a target value, print 'Yes' if the value exists in the tree, otherwise print 'No'. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N). The target is given on the next line.

Input: The first line contains space-separated level-order tokens ('N' for missing children) describing the BST. The second line contains a single integer - the target value to search for. Output: Print 'Yes' if the target exists in the tree, otherwise print 'No'.

1 <= number of nodes <= 10^5

This O(h) search is the ENTIRE reason BSTs are useful over plain unsorted structures - a general (non-BST) binary tree would require checking every single node, since there's no ordering to guide the search direction.

Check whether a specific value exists somewhere in a binary search tree. Brute force: Traverse the entire tree checking every node against the target - this costs O(n), unnecessary given the BST's ordering property, which lets you skip entire subtrees. Optimised: The BST property guarantees that at every step, only ONE direction could possibly contain the target - moving left or right based on a single comparison, and never needing to check both sides, bounds the search by the tree's height rather than its total size.

Treat the tree as if it were a plain binary tree with no ordering guarantee: traverse every node (DFS or BFS, visiting left and right children unconditionally) and compare each node's value to the target, printing "Yes" as soon as a match is found or "No" if the traversal finishes without one. This is always correct but completely ignores the BST property, so it can visit every single node even when the target is a few comparisons away from the root. Time: O(n) Space: O(n)

Exploit the BST ordering: at each node, compare the target to the node's value - if equal, found it; if smaller, recurse only into the left child; if larger, recurse only into the right child; recursing into an absent child means the value isn't present. Because only one child is ever explored at each level instead of both, the search only travels down a single root-to-leaf path, but that path is followed via recursive calls that consume stack space. Time: O(h) Space: O(h)

Use the identical BST comparison logic as the recursive version, but implement it with a simple while loop and a single "current node" pointer that moves left or right based on the comparison, stopping when it finds the target or falls off the tree (becomes null). This keeps the same single-path traversal benefit of using BST order, while eliminating the recursion call stack entirely, so extra memory use is constant regardless of the tree's height. Time: O(h) Space: O(1)

1. Start at the root. If the target equals the current node, found it - answer Yes. 2. If the target is SMALLER than the current node, move left; if LARGER, move right. 3. If you fall off the tree (reach a missing child) without finding a match, the value doesn't exist - answer No.

Time: O(h), where h is the tree's height - O(log n) for a balanced BST, O(n) worst case for a skewed one. Space: O(1) if implemented iteratively with a simple loop.

Test searching for the root's own value, a value smaller than every node and one larger than every node (both should quickly print 'No'), and n=10^5 nodes for performance.

This is the most fundamental BST operation - be ready to implement it instantly, both recursively and iteratively, since nearly every other BST problem builds on this exact search pattern.