Are decision tree algorithms linear or nonlinear Recently a friend of mine was asked whether decision tree algorithms are linear or nonlinear algorithms in an interview. I tried to look for answers to this question but couldn't find any satisfactory explanation. Can anyone answer and explain the solution to this question? Also, what are some other examples of nonlinear machine learning algorithms?
A decision tree is a non-linear mapping of X to y. This is easy to see if you take an arbitrary function and create a tree to its maximum depth.

For example:

if x = 1, y = 1
if x = 2, y = 15
if x = 3, y = 3
if x = 4, y = 27
...


Of course, this is a completely over-fit tree and won't generalize. But it demonstrates why a decision tree is a non-linear mapping.