Note: Tracing the origins for sayings and phrases is difficult in most cases, because it's hard pinpointing the one person or even location where it began to grow. What's provided are possibilities in how an idiom could have originated, along with early recorded forms of the saying. Usually, the expression will be found in old books, newspapers, poems, or plays.
However, if phrases are being commonly thrown around in forms of media, like a newspaper, that's usually an indicator to show it's already a well known phrase, and is probably much older. Ultimately, you get an approximate on how long a phrase has been used for, and gain a little understanding in where the saying could potentially be rooted from.
knowyourphrase.com - Sayings and Phrases - Meanings and Origins
To make a wrong assumption about someone or something.
If a person is being falsely accused of something, they might use this phrase to inform the accuser that they are mistaken.
It is believed that the origins of this phrase are rooted in hunting. Dogs are sometimes used during hunting because of their strong sense of smell, their ability to chase and track other creatures, and they add a bit of extra security for the hunter.
There will be times during a hunt where the dog chases a fleeing animal up a tree, but because dogs are not good climbers, they remain on the ground and bark instead. The barking indicates to the hunter where the fleeing animal is located. However, the will occasionally make a mistake and choose the wrong tree. Why? Well, there are a number of different factors. Perhaps the dog was unable to keep pace with the hunted animal during the chase, or maybe it got distracted along the way by something. Whatever the case, when the dog fails to pick the right tree, they are literally, 'barking up the wrong the tree.'
This expression goes back to at least the early 19th century, where this idiom is already being used in a figurative sense. For example, the Knickerbocker Magazine from 1836 reads:
"You've been barking up the wrong tree, cried the Ohioan."