What is the time complexity of pre order traversal in the iterative method of a binary tree?

Hi

I was asked this question today in class, and it is a good question! I will explain here and hopefully get my more formal answer reviewed or corrected where it is wrong. :)

Previous Answers

The observation by @Assaf is also correct since binary tree traversal travels recursively to visit each node once.

But!, since it is a recursive algorithm, you often have to use more advanced methods to analyze run-time performance. When dealing with a sequential algorithm or one that uses for-loops, using summations will often be enough. So, what follows is a more detailed explanation of this analysis for those who are curious.

The Recurrence

As previously stated,

T(n) = 2*T(n/2) + 1

where T(n) is the number of operations executed in your traversal algorithm (in-order, pre-order, or post-order makes no difference.

Explanation of the Recurrence

There are two T(n) because inorder, preorder, and postorder traversals all call themselves on the left and right child node. So, think of each recursive call as a T(n). In other words, **left T(n/2) + right T(n/2) = 2 T(n/2) **. The "1" comes from any other constant time operations within the function, like printing the node value, et cetera. (It could honestly be a 1 or any constant number & the asymptotic run-time still computes to the same value. Explanation follows.).

Analysis

This recurrence actually can be analyzed using big theta using the masters' theorem. So, I will apply it here.

T(n) = 2*T(n/2) + constant

where constant is some constant (could be 1 or any other constant).

Using the Masters' Theorem , we have T(n) = a*T(n/b) + f(n).

So, a=2, b=2, f(n) = constant since f(n) = n^c = 1, then it follows that c = 0 since f(n) is a constant.

From here, we can see that a = 2 and b^c = 2 ^0 = 1. So, a>b^c or 2>2^0. So, c < logb(a) or 0 < log2(2)

From here we have T(n) = BigTheta(n^{logb(a)}) = BigTheta(n^1) = BigTheta(n)

If your not famliar with BigTheta(n), it is "similar" ( please bear with me :) ) to O(n) but it is a "tighter bound" or tighter approximation of the run-time. So, BigTheta(n) is both worst-case O(n), and best-case BigOmega(n) run-time.

I hope this helps. Take care.

Traversing a binary tree recursively is usually the first approach to approaching binary tree problems. However, recursion could lead to large memory footprints, and often times interviewers will ask for an iterative traversal.

When traversing a tree iteratively, it is common to use a stack or a queue. The common pattern involves:

1) Determine whether to use a stack or a queue to store nodes we need to visit.

2) While our stack/queue is not null, retrieve nodes from it.

As an example, we can take a look at how to implement a preorder traversal iteratively.

Recall the recursive approach for a preorder traversal:

For the following tree:

Our preorder traversal would be: 1 -> 2 -> 4 -> 5 -> 3

At this point, we know a couple of things

• We want to visit roots before leaves
• We want to visit the left child before the right child.

1) Let's say, we visit each node with a stack. The first node we visit will always be the root. So in the example above, 1 is the root.

2) When we pop 1 from the stack, we have an option to add node 2 first or node 3 first. Which node should we push onto the stack first?

• Looking at what our traversal should end up being, 2 comes before 3, so if we want to see 2 first, we should probably add node 3 to the stack, followed by node 2. That way, when we pop a node from the stack, 2 will be popped before 3

At this point, we've printed 1 and our stack looks like this:

3) As our stack is not empty yet, we can pop from it again. We pop2, and we have to decide whether to push node 4 first or node 5.

• Again, if we look at our desired traversal outcome from our recursive approach, we see that 4 should be printed before 5. Following step 2a, it looks like we should push 5 onto the stack first, followed by 4.

• Now we've printed 1 2 and our stack looks like this:

  (4) (5) (3)

4) Again, we pop from our stack. This time 4 is popped and printed, and since 4 has no children, we don't push anything, and just keep popping.

• After 4 has been popped, the function printed 1 2 4 and our stack would then contain:

  (5) (3)

Looking at what we've been doing, it looks like a pattern has emerged.

1. Create an empty stack
2. Push root node onto stack
3. While our stack is not empty: a. pop node from the stack and print it b. push right child of popped node to stack. c. push left child of popped node to stack

Language: Python

Time complexity is O(n) since we push/pop each node of the tree, while space complexity is O(h), h being the height of the tree.

Going back to the beginning to see how we approached this problem from start to finish, there are a couple of important steps we followed:

1. Recall the recursive way to solve the problem
2. Working from the recursive solution, we know what our desired output should be
3. Using the desired output, we then tried to create a new approach that would give us the same outcome
4. Once we saw a pattern, we were able come up with an algorithm

Example problems

These are problems that can be solved with similar approaches of using stacks / queues

More resources