stack depth first search code example
Example 1: python depth first search
# left to right, pre-order depth first tree search, iterative. O(n) time/space
def depthFirstSearch(root):
st = [root]
while st:
current = st.pop()
print(current)
if current.right is not None: st.append(current.right)
if current.left is not None: st.append(current.left)
Example 2: python depth first search
# left to right, pre-order depth first tree search, recursive. O(n) time/space
def depthFirstSearchRec(root):
if root == None: return
print(root)
depthFirstSearch(root.left)
depthFirstSearch(root.right)
Example 3: depth first search stack
DFS-iterative (G, s):
let S be stack
S.push( s )
mark s as visited.
while ( S is not empty):
v = S.top( )
S.pop( )
for all neighbours w of v in Graph G:
if w is not visited :
S.push( w )
mark w as visited
DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)