  We contribute to the program of proving lower bounds on the size of branching
programs solving the Tree Evaluation Problem introduced by Cook et. al. (2012).
Proving a super-polynomial lower bound for the size of nondeterministic thrifty
branching programs (NTBP) would separate $NL$ from $P$ for thrifty models
solving the tree evaluation problem. First, we show that {\em Read-Once NTBPs}
are equivalent to whole black-white pebbling algorithms thus showing a tight
lower bound (ignoring polynomial factors) for this model.
  We then introduce a weaker restriction of NTBPs called {\em Bitwise
Independence}. The best known NTBPs (of size $O(k^{h/2+1})$) for the tree
evaluation problem given by Cook et. al. (2012) are Bitwise Independent. As our
main result, we show that any Bitwise Independent NTBP solving $TEP_{2}^{h}(k)$
must have at least $\frac{1}{2}k^{h/2}$ states. Prior to this work, lower
bounds were known for NTBPs only for fixed heights $h=2,3,4$ (See Cook et. al.
(2012)). We prove our results by associating a fractional black-white pebbling
strategy with any bitwise independent NTBP solving the Tree Evaluation Problem.
Such a connection was not known previously even for fixed heights.
  Our main technique is the entropy method introduced by Jukna and Z{\'a}k
(2001) originally in the context of proving lower bounds for read-once
branching programs. We also show that the previous lower bounds given by Cook
et. al. (2012) for deterministic branching programs for Tree Evaluation Problem
can be obtained using this approach. Using this method, we also show tight
lower bounds for any $k$-way deterministic branching program solving Tree
Evaluation Problem when the instances are restricted to have the same group
operation in all internal nodes.
