Decision trees: leaf-wise (best-first) and level-wise tree traverse
If you grow the full tree, best-first (leaf-wise) and depth-first (level-wise) will result in the same tree. The difference is in the order in which the tree is expanded. Since we don't normally grow trees to their full depth, order matters: application of early stopping criteria and pruning methods can result in very different trees. Because leaf-wise chooses splits based on their contribution to the global loss and not just the loss along a particular branch, it often (not always) will learn lower-error trees &quot;faster&quot; than level-wise. I.e. for a small number of nodes, leaf-wise will probably out-perform level-wise. As you add more nodes, without stopping or pruning they will converge to the same performance because they will literally build the same tree eventually.
Reference:
Shi, H. (2007). Best-first Decision Tree Learning (Thesis, Master of Science (MSc)). The University of Waikato, Hamilton, New Zealand. Retrieved from https://hdl.handle.net/10289/2317

EDIT: Regarding your first question, both C4.5 and CART are depth-first examples, not best-first. Here's some relevant content from the reference above:

1.2.1 Standard decision trees
Standard algorithms such as C4.5 (Quinlan, 1993) and CART (Breiman et al., 1984) for the top-down
induction of decision trees expand nodes in depth-first order in each
step using the divide-and-conquer strategy. Normally, at each node of
a decision tree, testing only involves a single attribute and the
attribute value is compared to a constant. The basic idea of standard
decision trees is that, first, select an attribute to place at the
root node and make some branches for this attribute based on some
criteria (e.g. information or Gini index). Then, split training
instances into subsets, one for each branch extending from the root
node. The number of subsets is the same as the number of branches.
Then, this step is repeated for a chosen branch, using only those
instances that actually reach it. A fixed order is used to expand
nodes (normally, left to right). If at any time all instances at a
node have the same class label, which is known as a pure node,
splitting stops and the node is made into a terminal node. This
construction process continues until all nodes are pure. It is then
followed by a pruning process to reduce overfittings (see Section
1.3).
1.2.2 Best-first decision trees
Another possibility, which so far appears to only have been evaluated in the context of boosting
algorithms (Friedman et al., 2000), is to expand nodes in best-first
order instead of a fixed order. This method adds the ”best” split node
to the tree in each step. The ”best” node is the node that maximally
reduces impurity among all nodes available for splitting (i.e. not
labelled as terminal nodes). Although this results in the same
fully-grown tree as standard depth-first expansion, it enables us to
investigate new tree pruning methods that use cross-validation to
select the number of expansions. Both pre-pruning and post-pruning can
be performed in this way, which enables a fair comparison between them
(see Section 1.3).
Best-first decision trees are constructed in a divide-and-conquer
fashion similar to standard depth-first decision trees. The basic idea
of how a best-first tree is built is as follows. First, select an
attribute to place at the root node and make some branches for this
attribute based on some criteria. Then, split training instances into
subsets, one for each branch extending from the root node. In this
thesis only binary decision trees are considered and thus the number
of branches is exactly two. Then, this step is repeated for a chosen
branch, using only those instances that actually reach it. In each
step we choose the ”best” subset among all subsets that are available
for expansions. This constructing process continues until all nodes
are pure or a specific number of expansions is reached. Figure 1.1
shows the difference in split order between a hypothetical binary
best-first tree and a hypothetical binary depth-first tree. Note that
other orderings may be chosen for the best-first tree while the order
is always the same in the depth-first case.