Traversal Complexities

Let's lay out our numeric conclusions for the traversal approaches:

Where ${N}$ is the tree's order, and ${H}$ is the tree's height.

The number of calls and stack sizes are all the same. Now, recall the Proper Binary Tree Bounds Lemma: The height of a tree, denoted ${H,}$ has the bounds:

where ${n}$ is the number of nodes. This yields the following complexities:

Where ${n}$ is the tree's order, and ${H}$ is the tree's height.

Thus, traversing an entire binary tree has a time complexity of ${O(n).}$ And the space complexity for such a traversal is at least ${O(\log n),}$ and at most ${O(n),}$ depending on the tree's height.