Tom looked in the direction that the stranger pointed, and beheld one of the great trees, fair and flourishing without, but rotten at the core...
The quote is slightly modified from its more familiar contemporary form: rotten at the core, instead of rotten to the core, which slightly changes the implications. "Rotten to the core" typically implies complete corruption, whereas "rotten at the core" implies a superficial health that disguises a deeper and fundamental corruption.
This phrase is used to describe one of the trees that belong to Old Scratch, which symbolize members of the local community. It is unclear if the trees have some kind of magical connection to the people they represent; for example, we don't know if harming the tree harms the person, or vice versa. At the least, they reflect one another, and the rotten core of this particular tree symbolizes a sinful affliction that underlies a more wholesome exterior.
The immediate relevance of this symbolism is to show that Old Scratch really is who he claims to be, in that "his" trees reflect private knowledge of others. This is also a social critique, implying that these societies were nowhere near as wholesome as they claimed to be.