Solutions to constrained linear model predictive control (MPC) problems can be pre-computed off-line in an explicit form as a piecewise linear (PWL) state feedback defined on a polyhedral partitioning of the state space. Even though real-time optimization is avoided, implementation of the PWL state feedback may still require a significant amount of computations. We suggest an algorithm that will determine an approximate explicit PWL state feedback solution by imposing an orthogonalsearch tree structure on the partition. This leads to efficient real-time computations and implementation at high sampling frequencies in embedded systems with inexpensive processors and low software complexity. The algorithm yield guarantees on the cost function error and constraint violations.