A tree that keeps numbers organized so you can find any of them by going left or right.
The idea (a sorted phone book as a tree)
A binary search tree (BST) follows one rule at every node: everything in the left subtree is smaller, everything in the right subtree is bigger. That is binary search turned into a shape: at each node you ask “is my number smaller or bigger?” and throw away half of what is left.
Search: start at the root. Equal? Found. Smaller? Go left. Bigger? Go right. Hit an empty spot (nil)? It is not there.
Insert: do exactly the same walk. The empty spot you fall into is where the new value belongs.
If the tree stays balanced, each step halves the problem, so lookups are fast. But the insert order matters: try inserting already-sorted numbers and see what happens to the shape.
Watch it work
Try it
Insert 10, 20, 30, 40, 50 (already sorted). What shape do you get? How many comparisons does searching for 50 need?
Insert the same numbers in the order 30, 20, 40, 10, 50. Compare the shape and the search cost.
Search for a value that is missing, like 55. Where does the search end?
Insert a duplicate such as 30, 30. What does this code do with it?
Common mistakes
Only checking the direct children. The rule is about the whole subtree, not just the next level.
Forgetting the nil case. Without if root == nil the recursion walks off the tree and panics on a nil pointer.
Assuming it is always fast. A sorted insert order makes a long “stick”, and every search becomes a slow walk down it.
Unclear duplicate rule. Decide up front whether duplicates are ignored, counted or sent to one side. This page ignores them.
Complexity, in plain English: a search or insert follows one path from the root, so it costs about the height of the tree. A balanced tree with 1,000,000 values has height about 20 (O(log n)); a stick-shaped tree has height n (O(n)).