Depth-first search is an algorithm for finding (or traversing) graph data structures. You start at the root and explore the branch as further as possible before going back (also called backtracking).

DFS written in Ruby:

def dfs(node, target)
  if node.value == target
    return node
  left = dfs(node.left, target) if node.left
  right = dfs(node.right, target) if node.right
  left or right