보통 역추적할 때는 일련의 잘못된 선택을 취소하는 방식으로 작업한다. 취소 횟수가 적을수록 더 빠르게 풀이를 찾아낼 수 있다. 최악의 시나리오에서는 역추적 알고리즘에서도 완전 검색의 경우와 마찬가지로 모든 가능한 풀이를 생성해야 할 수도 있지만 그런 경우는 흔치 않다.

역추적 알고리즘은 결정을 내리는 상황을 반영하는 트리를 구축하는 절차라고 생각하면 이해하기 쉽다. 전산학에서는 가계도나 조직도와 같은 계층 구조를 트리(tree)라고 부른다. 트리는 보통 뿌리(부모가 없는 유일한 노드)가 맨 위에, 잎(자식이 없는 노드)이 맨 아래쪽에 있는 형태로 그린다. 하지만 이런 표시 방식은 편의상 쓰이는 방법일 뿐이다. 역추적 알고리즘에서는 이런 트리를 상태 공간 트리(state-space tree)라고 부른다. 상태 공간 트리의 뿌리는 풀이 구축 절차의 시작점에 대응된다. 뿌리는 트리의 0번째 층이라고 생각할 수 있다. 뿌리의 자식 - 트리의 첫 번째 층 - 은 풀이의 첫 번째 구성 요소로 꼽을 수 있는 선택지(예를 들어 마방진을 구축할 때 1이 들어갈 자리)에 대응된다. 그리고 그 자식 - 두 번째 층에 있는 노드 - 은 풀이의 두 번째 선택지에 대응된다고 할 수 있다. 잎에는 두 가지 유형이 있다. 첫 번째 유형은 제대로 된 풀이로 이어질 수 없는 풀이에 대응되는 것으로 가망 없는 노드, 또는 막다른 골목이라고 부른다. 어떤 노드가 가망 없는 노드로 판단되면 역추적 알고리즘에서는 그 노드를 끝내고 (‘가지치기한다’라고 부른다) 해당 풀이 후보의 마지막 구성 요소와 관련된 결정을 모두 취소시키면서 가망 없는 노드의 부모 노드로 역추적해 올라가 그 구성 요소에 대한 다른 선택지를 시도해본다. 두 번째 유형의 잎은 정답 노드다. 풀이를 찾아내기만 하는 경우라면 거기서 끝내면 된다. 다른 풀이도 찾아야 한다면 그 잎의 부모로 역추적해 올라가 검색을 계속 수행한다.