This section is incomplete. Please feel free to edit this section to add missing information and complete it. Reason: Confirm that formulas/algorithms apply to both Gold/Silver and Crystal (and not only to one).
In Generation II, most outdoor areas contain a number of special trees () that Pokémon can use Headbutt on. These trees are distinct from other trees that either take up two vertical paces or that have rounded tops. When a Pokémon uses Headbutt on a tree, a wild Pokémon may drop out of the tree. Depending on the time of day, the Pokémon that falls out may be asleep. Some Pokémon can only be caught by this method (e.g., Pineco, Heracross).
All headbuttable trees contain wild Pokémon, but different trees have different chances of creating an encounter after Headbutt is used. The headbuttable trees in an area also generate their encounters from different sets of Pokémon depending on whether they have moderate encounter chances or low encounter chances. For example, on Route 44, trees with moderate encounter chances may only contain Spearow or Aipom, while trees with a low encounter chance may also contain Heracross.
Every headbuttable tree can be associated with an index from 0 to 9. Depending on the player's Trainer ID, half of those indices correspond to trees with moderate encounter chances, while the other half correspond to trees with a low encounter chance.
A tree's index depends on its X and Y coordinates in the map; that is, its distance from, respectively, the westmost and northmost edges.
To gain some insight into this formula, it is possible to "fix" one dimension and traverse the other, since X and Y are freely interchangeable. Substituting "Z" for one axis (the fixed axis) and "n" for the other (the axis that will be traversed), the formula becomes:
( ( Z * n + Z + n ) / 5 ) % 10
which then becomes:
( ( (Z + 1) * n + Z ) / 5 ) % 10
This result shows that, if a single row or column of trees is traversed (i.e., if n changes), moving from one tree to the next changes the index (before the modulo operation) by (Z + 1) / 5, where Z is the distance of that row or column from its origin edge (north or west). In short, the closer a row or column is to the edge (the smaller Z is), the slower the indices of those trees will change as the row or column is traversed.
The encounter chances associated with a tree of a given index are determined by a "pivot" index determined by the player's Trainer ID (specifically, the rightmost digit of the player's Trainer ID).
pivot = trainer_id % 10
If a tree's index matches the pivot index, its encounter chances are 80%; the next four tree indices (effectively, ( pivot + n ) % 10, where n = 1...4) have encounter chances of 50%; and the remaining indices have encounter chances of 10%. The 80% and 50% indices make up the "moderate" encounter chances referred to above, and share a common set of Pokémon from which encounters are created, while the 10% indices draw from a different set of Pokémon for encounters.
In Pokémon HeartGold and SoulSilver, Pokémon are not grouped by terrain, but now appear in specific locations. Unlike Generation II, not all trees will guarantee an encounter with a wild Pokémon. However, if a tree does cause a wild Pokémon to appear, there is a high chance of encountering a Pokémon again next time. Likewise, if no Pokémon appears when a tree is Headbutted, no Pokémon will ever appear for that tree. Repel cannot prevent Pokémon from appearing when headbutting a tree.
Also, the available Pokémon differ from tree to tree, as illustrated below.
An example of the population of two trees in Pewter City
For example, a tree in Pewter City may house Hoothoot, Pineco and Wurmple, while another in the same locality may house only Hoothoot and Wurmple. The level ranges may also differ for the same Pokémon. As such, not all Pokémon may be found in one tree within a specific location; the (Pewter City) table only reflects the lowest and highest possible level of all Pokémon found in the entire location.
This also explains why some Pokémon can only be found in a specific tree within that location (e.g. Starly in Pewter City or Taillow in Cherrygrove City). These trees are usually hidden, or only accessible via an HM move like Surf or Rock Climb.