When we have a graph (such as a tree or a binary tree) with information, it is very useful (and common) in the real world to visit the vertices/nodes of the graph looking for some info.
Depth First Search (DFS) is one of the most famous techniques to do this. This type of traversal visits nodes from top to bottom with only one condition: when visiting a node, you must visit the first (left) child of it, then the node itself, then the following child (to the right). Let's see an example with a binary search tree (which is a graph). Remember that a binary search tree is an ordered tree in which each node has at most two children.
Take a look at the following example:
DFS example
Try to apply this recursive pseudocode to the previous figure (in your mind), starting from the root node:
public func depthFirstSearch(node:TreeNode) {
depthFirstSearch(node.leftChild)
print(node.value)
depthFirstSearch(node.rightChild)
}As you can see, we have a binary...