Decision trees provide a rich family of highly non-linear but efficient\nmodels, due to which they continue to be the go-to family of predictive models\nby practitioners across domains. But learning trees is challenging due to their\ndiscrete decision boundaries. The state-of-the-art (SOTA) techniques resort to\n(a) learning \\textit{soft} trees thereby losing logarithmic inference time; or\n(b) using methods tailored to specific supervised learning settings, requiring\naccess to labeled examples and loss function. In this work, by leveraging\ntechniques like overparameterization and straight-through estimators, we\npropose a unified method that enables accurate end-to-end gradient based tree\ntraining and can be deployed in a variety of settings like offline supervised\nlearning and online learning with bandit feedback. Using extensive validation\non standard benchmarks, we demonstrate that our method provides best of both\nworlds, i.e., it is competitive to, and in some cases more accurate than\nmethods designed \\textit{specifically} for the supervised settings; and in\nbandit settings, where most existing tree learning techniques are not\napplicable, our models are still accurate and significantly outperform the\napplicable SOTA methods.\n