Trees and Harry Potter's Triwizard tournament

This post is the seventh of a series adapted from my conference talk, Fun, Friendly Computer Science.

My favorite book in the Harry Potter series is the fourth, “Harry Potter and the Goblet of Fire.” If you're a big Harry Potter fan, you probably enjoyed the end of that book which featured a giant maze full of magical obstacles. The first person to the center of the maze won the Triwizard cup. There were 2 people from Harry’s school competing to win, Harry and Cedric. When they were racing through the maze, they were faced with decisions about whether to go left or right or in some cases continue straight down the center path.

Modeling these choices can be done using a tree data structure. Unlike linked lists, stacks, or queues, trees are useful to model hierarchical data (think file systems or organization charts).

In a tree data structure, there is a root node that has one to many children—in much the same way that a linked list stores a reference to the next node in the list. To access other nodes in the tree, you must traverse through the nodes.

There are two common algorithms for traversing the nodes of a tree, breadth-first search and depth-first search. We’ll model Harry and Cedric’s path through the Triwizard maze to illustrate these two search algorithms.

Breadth-first search

Breadth-first search (BFS) is when you traverse the nodes one level at a time, visiting all the nodes on level 1, then level 2 and so on. Because BFS considers all of a node's neighbors before continue deeper into the tree, it is not the best search algorithm to use in decision-making problems like finding the center of a maze quickly.

In “Harry Potter and the Goblet of Fire,” Harry is the young and inexperienced competitor. He doesn’t know as much magic as Cedric and is at a significant disadvantage in the tournament. So I’ve chosen to model his decision path as BFS to reflect that.

In the gif, you can see that Harry’s route starts at node 1 and continues to level 2 with node 3. Node 3 isn’t the center of the maze, so he moves laterally to node 4 to check other neighboring nodes in level 2. Once he’s visited all of the nodes on level 2, he continues to level 3 with node 7. Again, since node 7 isn’t the center of the maze he checks neighboring nodes in level 3 before continuing to level 4 and so on until he finds the center of the maze on level 5. Using BFS (which is not the optimal algorithm in this case) requires that Harry visit a total of 8 nodes before he finds the center of the maze.

Code samples

I have code samples on my Github in Javascript, Ruby, and Python. I’ll be using Javascript samples in this post but check out the other samples if you’re more familiar with those languages.

In both the iterative and recursive implementations of the BFS algorithm, a queue is used to keep track of nodes that have already been visited. If you'd like a refresher on recursion, I have a previous post about recursion and Russian nesting dolls.

Iterative implementation

iterativeBreadthFirstSearch(rootNode, successCriteria) {
  // Check that a root node exists.
  if (rootNode === null) return;

  // Create our queue and push our root node into it.
  const visitedNodes = new Queue();
  visitedNodes.enqueue(rootNode);
  let foundNode, currentNode;
  const searchPath = [];

  // Continue searching through queue as long as it's not empty.
  while (visitedNodes.tail !== null && !foundNode) {
    currentNode = visitedNodes.dequeue().data;
    searchPath.push(currentNode.data.name);

    foundNode = successCriteria(currentNode);
    if (foundNode) searchPath.push("Success!”);

    for (let child of currentNode.children) {
      if (child) {
        visitedNodes.enqueue(child);
      }
    }
  }

  return searchPath;
}

Recursive implementation

recursiveBreadthFirstSearch(rootNode, successCriteria) {
  const visitedNodes = new Queue();
  visitedNodes.enqueue(rootNode);
  const searchPath = [];
  this.recursiveBFSLogic(visitedNodes, successCriteria, searchPath);
  return searchPath;
}


recursiveBFSLogic(visitedNodes, successCriteria, searchPath) {
  if (visitedNodes.tail === null) {
    return; // if the queue is empty, we're done.
  }

  const currentNode = visitedNodes.dequeue().data;
  searchPath.push(currentNode.data.name);

  const foundNode = successCriteria(currentNode);

  if (foundNode) {
    searchPath.push("Success!");
    visitedNodes = new Queue(); // if we found a successful path, we're done
  } else {
    for (let child of currentNode.children) {
      if (child) {
        visitedNodes.enqueue(child);
      }
    }
  }

  this.recursiveBFSLogic(visitedNodes, successCriteria, searchPath);
}

Depth-first search

Depth-first search (DFS) is when you traverse the nodes as deep as possible from one side of the tree to the other. Because DFS looks as deep into the tree as possible before moving to neighboring nodes it is the more suitable search algorithm for decision making, like finding the center of a maze.

In “Harry Potter and the Goblet of Fire,” Cedric is the older, better wizard. He has an advantage in the tournament because he knows more magic and has more experience. I’ve chosen to model his decision path as DFS to reflect that.

In the gif, you can see that Cedric's route starts at node 2 which has children, so he moves a level deeper to one of the children on level 2, node 6. Node 6 has children so he continues deeper to level 3 node 10, which has children so he continues to node 15. Node 15 doesn’t have children so he moves laterally to check its neighboring nodes for children. Node 14 has children so he continues deeper in the tree with node 19. He continues traversing as deep as possible before moving laterally to search for more children which eventually leads him to find the center of the maze on level 7, node 24. Using DFS (which is the optimal algorithm) requires Cedric to visit a total of 10 nodes before he finds the center of the maze.

Code samples

In both the iterative and recursive implementations of the DFS algorithm, a stack is used to keep track of nodes that have already been visited.

Iterative implementation

iterativeDepthFirstSearch(rootNode, successCriteria) {
  // Check that a root node exists.
  if (rootNode === null) return;

  // Create our queue and push our root node into it.
  const visitedNodes = new Stack();
  visitedNodes.push(rootNode);
  let foundNode, currentNode;
  const searchPath = [];

  // Continue searching through stack as long as it's not empty.
  while (visitedNodes.head !== null && !foundNode) {
    currentNode = visitedNodes.pop().data;
    searchPath.push(currentNode.data.name);

    foundNode = successCriteria(currentNode);
    if (foundNode) searchPath.push("Success!");

    for (let child of currentNode.children) {
      if (child) {
        visitedNodes.push(child);
      }
    }
  }

  return searchPath;
}

Recursive implementation

recursiveDepthFirstSearch(rootNode, successCriteria) {
  const visitedNodes = new Stack();
  visitedNodes.push(rootNode);
  const searchPath = [];
  this.recursiveDFSLogic(visitedNodes, successCriteria, searchPath);
  return searchPath;
}

recursiveDFSLogic(visitedNodes, successCriteria, searchPath) {
  if (visitedNodes.head === null) {
    return; // if the stack is empty, we're done.
  }

  const node = visitedNodes.pop().data;
  searchPath.push(node.data.name);

  const foundNode = successCriteria(node);

  if (foundNode) {
    searchPath.push("Success!");
    visitedNodes = new Stack(); // if we found a successful path, we're done
  } else {
    for (let child of node.children) {
      if (child) {
        visitedNodes.push(child);
      }
    }
  }
  this.recursiveDFSLogic(visitedNodes, successCriteria, searchPath);
}

Conclusion

You may have noticed that Harry used the worse algorithm, BFS, but still managed to find the center of the maze in fewer steps than Cedric who used the better algorithm, in this case, DFS. I won’t share spoilers (it was published almost 20 years ago...), but there is a villain in the book that wanted Harry to win the tournament for nefarious reasons. The villain cheated, removing obstacles from Harry’s path while making it more difficult for Cedric and other competitors to get to the center. If you look at the tree used to model Harry and Cedric’s path through the maze you’ll notice that both Harry’s best and worst route through the maze was shorter than Cedric’s best path. The villain made sure that no matter what, Harry would have an easier time winning.