tree - Non-recursive depth first search algorithm

DFS:

list nodes_to_visit = {root}; while( nodes_to_visit isn't empty ) {   currentnode = nodes_to_visit.take_first();   nodes_to_visit.prepend( currentnode.children );   //do something } 

BFS:

list nodes_to_visit = {root}; while( nodes_to_visit isn't empty ) {   currentnode = nodes_to_visit.take_first();   nodes_to_visit.append( currentnode.children );   //do something } 

The symmetry of the two is quite cool.

Update: As pointed out, take_first() removes and returns the first element in the list.

You would use a stack that holds the nodes that were not visited yet:

stack.push(root) while !stack.isEmpty() do     node = stack.pop()     for each node.childNodes do         stack.push(stack)     endfor     // … endwhile 

If you have pointers to parent nodes, you can do it without additional memory.

def dfs(root):     node = root     while True:         visit(node)         if node.first_child:             node = node.first_child      # walk down         else:             while not node.next_sibling:                 if node is root:                     return                 node = node.parent       # walk up ...             node = node.next_sibling     # ... and right 

Note that if the child nodes are stored as an array rather than through sibling pointers, the next sibling can be found as:

def next_sibling(node):     try:         i =    node.parent.child_nodes.index(node)         return node.parent.child_nodes[i+1]     except (IndexError, AttributeError):         return None 

Use a stack to track your nodes

Stack<Node> s;  s.prepend(tree.head);  while(!s.empty) {     Node n = s.poll_front // gets first node      // do something with q?      for each child of n: s.prepend(child)  } 

An ES6 implementation based on biziclops great answer:

root = {    text: "root",    children: [{      text: "c1",      children: [{        text: "c11"      }, {        text: "c12"      }]    }, {      text: "c2",      children: [{        text: "c21"      }, {        text: "c22"      }]    }, ]  }    console.log("DFS:")  DFS(root, node => node.children, node => console.log(node.text));    console.log("BFS:")  BFS(root, node => node.children, node => console.log(node.text));    function BFS(root, getChildren, visit) {    let nodesToVisit = [root];    while (nodesToVisit.length > 0) {      const currentNode = nodesToVisit.shift();      nodesToVisit = [        ...nodesToVisit,        ...(getChildren(currentNode) || []),      ];      visit(currentNode);    }  }    function DFS(root, getChildren, visit) {    let nodesToVisit = [root];    while (nodesToVisit.length > 0) {      const currentNode = nodesToVisit.shift();      nodesToVisit = [        ...(getChildren(currentNode) || []),        ...nodesToVisit,      ];      visit(currentNode);    }  }