Complexities of binary tree traversals

Question

What is the time complexity of inorder postorder and preorder traversal of binary trees in data structures   Is it O n  or O log n  or O n 2

User · Answer

Introduction

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.

User · Answer

O n   because you traverse each node once  Or rather - the amount of work you do for each node is constant  does not depend on the rest of the nodes

User · Answer

T n    2T n 2   c   T n 2    2T n 4    c    T n    4T n 4    2c   c   similarly               T n    8T n 8    4c  2c   c              last step     T n    nT 1    c sum of powers of 2 from 0 to h height of tree    so Complexity is O 2  h 1  -1   but h   log n    so  O 2n - 1    O n

User · Answer

Depth first traversal of a binary tree is of order O n   Algo --  lt b gt      PreOrderTrav   -----------------T n  lt b gt      if root is null---------------O 1  lt b gt        return null-----------------O 1  lt b gt      else -------------------------O 1  lt b gt        print root -----------------O 1  lt b gt        PreOrderTrav root left -----T n 2  lt b gt        PreOrderTrav root right ----T n 2  lt b gt   If the time complexity of the algo is T n  then it can be written as T n    2 T n 2    O 1   If we apply back substitution we will get T n    O n

User · Answer

O n  I would say   I am doing for a balanced tree applicable for all the trees  Assuming that you use recursion   T n    2 T n 2    1 ----------   1   T n 2  for left sub-tree and T n 2  for right sub-tree and  1  for verifying the base case   On Simplifying  1  you can prove that the traversal either inorder or preorder or post order  is of order O n

User · Answer

Travesal is O n  for any order - because you are hitting each node once   Lookup is where it can be less than O n  IF the tree has some sort of organizing schema  ie binary search tree

User · Answer

In-order  Pre-order  and Post-order traversals are Depth-First traversals   For a Graph  the complexity of a Depth First Traversal is O n   m   where n is the number of nodes  and m is the number of edges   Since a Binary Tree is also a Graph  the same applies here  The complexity of each of these Depth-first traversals is O n m    Since the number of edges that can originate from a node is limited to 2 in the case of a Binary Tree  the maximum number of total edges in a Binary Tree is n-1  where n is the total number of nodes   The complexity then becomes O n   n-1   which is O n

User · Answer

Consider a skewed binary tree with 3 nodes as 7  3  2  For any operation like for searching 2  we have to traverse 3 nodes  for deleting 2 also  we have to traverse 3 nodes and for for inserting 1 also  we have to traverse 3 nodes  So  binary tree has worst case complexity of O n

[time-complexity] Complexities of binary tree traversals

Introduction

Previous Answers

The Recurrence

Explanation of the Recurrence

Analysis

Examples related to time-complexity