Question: How weigth order affects the computing cost in a backtracking algorithm? The number of nodes and search trees are the same but when it's non-ordered it tooks a more time, so it's doing something.

Thanks!

Answer: 
Sometimes in backtracking algorithms, when you know a certain branch is not an answer - you can trim it. This is very common with agents for games, and is called [Alpha Beta Prunning](http://en.wikipedia.org/wiki/Alpha-beta_pruning).

Thus - when you reorder the visited nodes, you can increase your prunning rate and thus decrease the actual number of nodes you visit, without affecting the correctness of your answer.

One more possibility - if there is no prunning is cache performance. Sometimes trees are stored as array [especially [complete trees](http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees)]. Arrays are most efficient when iterating, and not "jumping randomly". The reorder might change this behavior, resulting in better/worse cache behavior.
The essence of **backtracking** is precisely **not looking at all possibilities** or nodes (in this case), however, **if the nodes are not ordered** it is impossible for the algorithm to "prune" a possible branch because it **is not known with certainty if the element Is actually on that branch**. 

**Unlike** when it is an ordered tree since if the searched element is **greater / smaller** the root of that subtree, the searched element is to the **right or left** respectively. That is why if the tree is not ordered the computational order is equal to brute force, however, if the tree is ordered in the worst case order is equivalent to brute force, but the order of execution is smaller.