Given the following code, in what order will we visit the nodes?

hello there, can someone please explain how the tree is traversed in this quiz, how the value travels through the traverse function:

class TreeNode:
  def __init__(self, value):
    self.value = value
    self.children = []

  def add_child(self, child_node):
  def traverse(self):
    nodes_to_visit = [self]
    while len(nodes_to_visit) > 0:
      current_node = nodes_to_visit.pop()
      nodes_to_visit += current_node.children

root = TreeNode("A")
first_child = TreeNode("B")
second_child = TreeNode("C")



does “A” “B” “C” go into the ‘node_to_visit’ list when it is called by ‘root.traverse’ ??

if so, while ‘current_node’ starts to .pop() the values, why do we have this line ‘nodes_to_visit += current_node.children’.
doesnt this line make the loop infinite because we are popping and adding again?


The key concept to understand here on how traversing a tree works, is that you start with the root node (that’s why the first nodes_to_visit is self), and then you go from the root to its children, and from the children to their children, and so on… until you have no more nodes left.

This is why when you’re done traversing a node, you pop() it, and then add its children so that you can continue traversing down the line.

Pop()-ing a node removes it from the list, so you don’t go over the same node twice, so the loop is not infinite. And when you add its children, you don’t add the parent node as well, so you’re never adding the same node twice either.

1 Like

OH OK GOT IT we are always adding the child of the current node!!!

one last question if you have time, how come the order of traversing starts A => C => B ?
i didnt quite get that part either.

thanks a lot

No problem!

Try to visualize the tree nodes and their relationships, and the order in which they are added and removed to the traversal, and you’ll figure it out yourself.

The root node here is “A”, it’s child is “B”, and "B"s child is “C”.

You start traversing with the root “A”, so this is how the list looks ["A"], then you pop() it, now you have an empty list [], then you add "A"s children (note that here you’re adding its direct children only). Then you pop() "A"s only child… You see where this is going? :slightly_smiling_face:

Ah sorry, I just noticed that you’re asking why it’s going “A”, “C”, then “B”, and that “B” and “C” are both direct children of “A”.

Well, to understand this then, you have to look at the order the children were added, and remember that pop() removes the last element from a list by default.

1 Like

oh ok thanks for the message, so basically because it removes the last element, i guess thats why we will visit the elements A => C => B