Binary Search Tree Includes

Given a binary search tree and a target, return true if the target is present. Use the BST ordering to search in O(height), not O(n).

bstIncludes(root, target)

Input format: tree | target (the tree is a valid BST in level-order form).

Examples

(5 3 8 2 4 7 9), target=7   // → true
(5 3 8 2 4 7 9), target=6   // → false
(empty), target=1           // → false

Walkthrough

Thinking it through

Searching an arbitrary binary tree means checking every node — no guarantee about how values are arranged. A BST is different: at every node, everything in the left subtree is smaller, everything in the right is larger. That guarantee lets you skip most of the tree, the same way binary search on a sorted array skips most of the array.

The core intuition: ordering prunes the search space

At any node, ask: is the target smaller, larger, or equal? Equal means done. Smaller means the target can't exist anywhere in the right subtree — discard it entirely, continue left. Larger means discard the left subtree, continue right. Same idea as binary search: each comparison eliminates roughly half the remaining candidates in one shot.

Building the approach

Start at the root. Compare target to the node's value: match means present; smaller means go left; larger means go right. Repeat at whichever node you land on. Reaching a missing node means the target was never there — the BST ordering guarantees exactly which path would have led to it, and you've followed that path to its end.

Why this is efficient

Each step discards an entire subtree, so comparisons are bounded by the tree's height, not its node count. A roughly balanced BST gives O(log n) typical time, O(h) in general (degrading toward O(n) only for very unbalanced trees, e.g. from inserting already-sorted data). Following a single path down needs only O(1) extra space.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.