1

I have been doing problems on LeetCode recently, and keep getting stuck on some graph or tree problems. I understand the underlying concepts of Graphs, Trees, and different methods of traversal just fine. For example, I can code a tree from scratch by creating a class for the Node and then passing the root to a function that traverses the tree using these interconnected node objects.

Example below.

class TreeNode():
    def __init__(self,val=None,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right

def BFS_tree(root):
    queue = [root]

    while queue:
        node = queue[0]
        print(node.val)
        queue = queue[1:]
        left = node.left
        right = node.right
        if left:
            queue.append(node.left)
        if right:
            queue.append(node.right)

What I have trouble with is applying this when the input data structure is not already an object specially created for representing part of a Graph or a Tree.

For example, I see problems where you are supposed to use a DFS on a 2D array, with each second-level element vertex and the edges connected by i+1 and i-1 (Example)

Or array of numbers representing a combo lock where each combo 0000-9999 is a possible element on a graph (Example)

Or an array representing the BFS traversal of a tree that then must be used to delete certain elements and keep track of the disjointed trees that result (Example)

At a very high level, this makes perfect sense.

But I don't really understand how to actually code it. What are some generalized approaches I can use when thinking of a different data structure in terms of a Graph or Tree. Obviously the approach of init a Node Object, populating the graph with a Node representation of every element, and then traversing it would work... but is far too much work, especially since I want to solve these problems quickly such as in a interview!

1

The first thing to realize is that the graphs/trees that you need to operate on in those problems aren't necessarily explicit.

For the island finding problem you have an explicit graph (the map) and standard maze-solving techniques apply. To summarize, simply traverse the array running BFS or DFS from any nodes representing land. You'll need to keep a taboo list of visited nodes to avoid cycles.

The lock problem has an implicit tree of moves between lock states. This is what you execute your search algorithm against. Note that you don't need to represent the entire tree in memory at once.

The disjoint tree problem isn't well-formed. Not all binary trees are balanced (but the problem seems to assume it), you're asked to return resulting roots (but the example returns full trees), etc.

If you can get your hands on a copy of Russell & Norvig's text on Artificial Intelligence you'll find it instructive. Many AI techniques ultimately boil down to some form of search on an infinite tree or graph.

  • Thanks! I still am unsure of how to approach these problems, but this provides a good place to start I think. Also I think I still have R&N's book on AI somewhere in my parent's house, haha. – Brian C May 21 '20 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.