Tags: depth first search, trees
What is the time complexity of depth first search (DFS) when run on a tree with \(n\) nodes?
\(\Theta(1)\)
\(\Theta(\log n)\)
\(\Theta(n)\)
\(\Theta(n \log n)\)
\(\Theta(n^2)\)
\(\Theta(n^3)\)