CODEWITHSUNDEEP
pythonpython-3.x
JacobIRR
JacobIRR

Reputation: 8946

Which x-order tree traversal (depth first search) is being used here?

This leetcode question is solved quickly using some depth-first traversal since it involves subsets:

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        results = []

        if candidates == None or len(candidates) == 0:
            return results

        candidates = sorted(candidates)

        combination = []
        self.recurse(results, combination, candidates, target, 0)

        return results

    def recurse(self, results, combination, candidates, target, startIndex):
        '''
        walk the tree, looking for a combination of candidates that sum to target
        '''
        print("combination is : " + str(combination))
        if target == 0:
            # must add a copy of the list, not the list itself
            results.append(combination[:])
            return;

        for i in range(startIndex, len(candidates)):
            if candidates[i] > target:
                break

            combination.append(candidates[i])
            self.recurse(results, combination, candidates, target - candidates[i], i)
            combination.remove(combination[len(combination) - 1])

s = Solution()
results = s.combinationSum([2,6,3,7], 7)
print(results)
assert results == [[2, 2, 3], [7]]

...However, I cannot tell exactly which type of traversal is used here. I recognize in-order traversal when I see the use of "nodes" and "left"/"right" properties like this:

def inorder(node):
  if node == None: return
  inorder(node.left)
  do_something_with_node(node)
  inorder(node.right)

...but the references to nodes and left/right children are not explicit in this solution. "Nodes" are subsets of the candidates list in this case, but is this in-order traversal? Or pre/post-order?

*Update: I printed the combination at the top of recurse and got this:

combination is : []
combination is : [2]
combination is : [2, 2]
combination is : [2, 2, 2]
combination is : [2, 2, 3]
combination is : [2, 3]
combination is : [3]
combination is : [3, 3]
combination is : [6]
combination is : [7]

Upvotes: 0

Views: 36

Answers (1)

Primusa
Primusa

Reputation: 13498

This is a pre-order traversal. This means the order it visits nodes in is (root, children). The recurse function is essentially a glorified version of:

def depth_first_search(state):

    if state is solution:
        results.append(state)
    for next_state in next_possible_states:
        if next_state is valid:
            depth_first_search(next_state)

First it visits the current node and checks if it's a solution. Then it moves on to the children. Pre-order traversal.

Upvotes: 1

Related Questions