Tree Traversal

Item	DFS	BFS
Data Structure	Stack	Queue
Vertex Order	one sequence	two sequences
Time Complexity	$O(n)$	$O(n)$
Space Complexity	$O(height)$	$O(width)$
Worst-case Space Complexity	$O(n)$	$O(n)$

Example

Tree Node definition

DFS

BFS

Level Order Traversal

Preorder Traversal

Inorder Traversal

Postorder Traversal

Tests