A binary search tree organizes values so comparisons can select one subtree at each step. Under a strict ordering, every value in a node's left subtree is smaller and every value in its right subtree is larger. The recording explains that rule, navigation, and common operations. Duplicate keys need an additional policy if the API permits them.
Apply the rule to entire subtrees
Suppose the root is 10, its left child is 5, and 5 has a right child of 12. The local edge from 5 to 12 appears ordered, but 12 violates the root's left-subtree constraint. Checking only a node against its immediate children cannot validate the full tree. Ancestor bounds remain relevant farther down the path.
Searching uses those bounds in the other direction. A target below the current value can only be in the left subtree; a larger target can only be in the right. If the selected child does not exist, the search is complete without scanning the opposite subtree. That exclusion argument depends on the tree actually satisfying the ordering invariant.
Explain extrema and shape
The minimum is reached by following left links until none remains. That node can still have a right child, so it need not be a leaf. The maximum follows the corresponding right-link path and can have a left child. The recording's correction clarifies that distinction.
Operation costs depend on height. A balanced tree can provide logarithmic-height paths, while an unbalanced tree can become a chain. Inserting already sorted values into an ordinary unbalanced implementation illustrates this worst case. Naming the structure a binary search tree does not promise self-balancing behavior.
Keep result shape and duplicate policy explicit
A search might return a matching node, a boolean, or a stored value. The implementation lesson returns a node or an absent result. If equal values are allowed, decide whether insertion ignores them, stores counts, or consistently places them on a chosen side. Validation must use the same policy.
Continue with Implement a Binary Search Tree to trace insert and search. Then try BST Validate, whose inherited bounds catch the 12-under-5 counterexample. Use Tree Traversal to connect in-order visits with sorted output under the strict invariant.
Search by eliminating one subtree at a time
For the heap-indexed tree [8, 3, 10, 1, 6, null, 14], a search for 6 compares with 8, follows the left child to 3, and then follows the right child to 6. A search for 7 reaches an absent child and returns false. The function assumes that the supplied tree already satisfies the ordering contract.
The example stores children at positions 2i + 1 and 2i + 2, with null slots marking missing nodes. A null root is an empty tree. Slots beneath an absent parent are unreachable. This representation is useful for a small worked example; it is not a recommendation for storing a very sparse production tree.
Relate the cost to height
Each comparison follows at most one child, giving O(h) time for height h and O(1) additional storage in the iterative implementation. A balanced tree makes h logarithmic in its node count. A chain makes h linear. The search function does not rebalance the input or verify all ordering constraints first.
Check the root, both extreme values, an absent value between existing keys, an empty tree, and a singleton. The complete insertion lesson allows equal keys on the right. The separate validate BST exercise uses its own stricter validation contract; read that contract before sharing duplicate-handling assumptions across the two tasks.
Go example and implementation choices
Each nonnil *int slot supplies a key for comparison, while nil ends the path. The function does not allocate or change the pointed-to values. Integer slice indices implement the heap layout directly. Concurrent payload mutation would break the stable-order assumption and needs an external synchronization policy; the simple search example assumes its input stays fixed throughout the call.
Worked example
func ContainsBST(values []*int, target int) bool {
index := 0
for index < len(values) && values[index] != nil {
value := *values[index]
if value == target { return true }
if target < value { index = 2*index+1 } else { index = 2*index+2 }
}
return false
}
Continue in Go
Open Binary Search Trees for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the Go example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The Go interview preparation guide connects these language choices with further practice and the cross-language operation reference.