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.
The origin of this phrase is believed to be rooted in dogs and hunting. Dogs are sometimes used during hunting because of their strong sense of smell, their ability to chase and track other animals, and they add a bit of extra security for the hunter.
After spotting another animal, a dog will likely give chase. The fleeing animal, if it is capable, may decide to climb a tree in order to get away. However, since dogs are not great at climbing trees, they will instead remain at the trunk of the tree and bark, which gives the hunter an indication on where the fleeing animal went.
Well, a dog can make a mistake and choose the wrong tree. How would the dog get it wrong? Well, there are a number of factors that could have led to the mistake. Perhaps the dog was unable to keep pace with the fleeing animal during the chase, or maybe it got distracted along the way by something. Whatever the case, if a dog fails to pick the right tree, well, then they are literally 'barking up the wrong the tree.'
This expression goes back to at least the earlyish 19th century, where the 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."