Perhaps the most obvious starting place, the venus flytrap is a plant with “jaws” that slam shut like a bear trap when the hairs on the inside are moved. Typically it requires several movements within a certain time frame in order to trigger the jaws to shut (so the plant knows that the thing inside its jaws is a creature and not a leaf or debris). Once closed, the jaws fill with a digestive fluid which breaks down the prey.
Applying this to your tree, there may be giant jaws like those of a venus flytrap scattered around the base of the tree. The jaws would be connected to the tree via an underground stem which runs from the jaws to the base of the tree. The actual tree portion looks pretty normal, perhaps mimicking other trees via interbreeding or simply evolving to look like, for example, a common oak tree or a fir tree. This has been seen in both snakes and insects where one species evolves to look like another.
Sweet, Delicious, Poison
Your tree may evolve poisonous fruit, slowly killing any large animal that ate it. In fact, apple seeds have cyanide in them. Well, to be more specific, they have a compound in them called Amygdalin that breaks down into hydrogen cyanide.
Amygdalin is a part of the seeds' chemical defenses. It is harmless when intact, but when the seeds are damaged, chewed or digested, amygdalin degrades into hydrogen cyanide. This is very poisonous and even lethal in high doses.
The fruits of your trees could contain far more Amygdalin, perhaps the entire fruit is laced with it. When a creature bites down into the fruit, the compound would start to degrade into lethal amounts of hydrogen cyanide and kill the creature relatively quickly. The fruits should have some sweeteners in them as well to encourage an animal to chew and swallow the fruit, making the poison more effective (i would imagine, based on apple seeds, that Amygdalin would make the fruit very bitter. By adding sweeteners, such as high amounts of sugar, this could help to mask the taste).
Once dead, the animal would start to decompose, providing nutrients to the tree. Scavengers may also be killed indirectly by consuming part of the poisoned creature. By eating the cyanide filled carcass, the scavenger in turn would be poisoned and die, providing more nutrients to the tree.
All of a sudden this makes the story of Snow White eating a poisoned apple and dying make sense, and gives it a much darker tone.
You May Feel a Little Pinch
As one of your challenge conditions is to have the tree covered in “something that resembles leaves or needles”, i propose something similar to Nettles. These are brightly green coloured plants covered in hypodermic needles that inject toxins into a creature that touches them.
You could have something like pine needles, found on pine trees, which function in a similar way. These needles could inject a toxin into an animal that touches the tree, quickly killing it. It may be hydrogen cyanide, as mentioned earlier, but to spice things up a bit i’ll also add in neurotoxins. These are toxins that affect the nervous system, your trees could paralyse its prey or give it a heart attack, killing the creature. Again, it would slowly decompose and provide nutrients to the tree. Any creature that got near risks touching the tree and being killed as well.
Simply because i love the idea of the leaves from a willow tree triggering some kind of trap. When a creature passes through the vines, it causes the tree to release toxic chemicals to kill said creature, perhaps in the form of pollen or some kind of gas or mist released from the tree.
The tree may have some internal requirements to trigger the release of its poison. For example, a small section the leaves parting and closing again with no other movement for a short period of time. This would prevent premature triggering due to the wind or debris. The leaves may also only grow a certain length, allowing very small animals to pass underneath and not trigger the trap (as it may be more effort than its worth to poison a single squirrel, for example.) However, larger animals would still trigger it as they are too big to go under the leaves.
Also, quick reference to Nausicaä, Valley of the Wind
Whilst not carnivorous trees, the plants release a toxic spore which kills any creature that inhales it. This idea could easily be translated to create carnivorous trees.