Time and Space Complexity Analysis of Tree Traversal Algorithms

Let us discuss the Time and Space complexity of different Tree Traversal techniques, such as Inorder Traversal, Preorder Traversal, Postorder Traversal, etc.

Time Complexity of Tree Traversal Algorithms

Let us see different corner cases:

Complexity function T(n) — for all problems where tree traversal is involved — can be defined as: 

T(n) = T(k) + T(n – k – 1) + c,  where k is the number of nodes on one side of the root and n-k-1 on the other side.

Let’s do an analysis of boundary conditions:

Case 1: Skewed tree (One of the subtrees is empty and another subtree is non-empty )
k is 0 in this case. 
T(n) = T(0) + T(n-1) + c 
T(n) = 2T(0) + T(n-2) + 2c 
T(n) = 3T(0) + T(n-3) + 3c 
T(n) = 4T(0) + T(n-4) + 4c
………………………………………… 
…………………………………………. 
T(n) = (n-1)T(0) + T(1) + (n-1)c 
T(n) = nT(0) + (n)c
Value of T(0) will be some constant say d. (traversing an empty tree will take some constants time)
T(n) = n(c+d) 
T(n) = Θ(n) (Theta of n)

Case 2: Both left and right subtrees have an equal number of nodes.
T(n) = 2T(n/2) + c 
This recursive function is in the standard form (T(n) = aT(n/b) + Θ(n) ) for master method. If we solve it by master method we get Θ(n)

Auxiliary Space of Tree Traversal Algorithms

O(1) If we don’t consider the size of the stack for function calls then O(1) otherwise O(h) where h is the height of the tree. 

Note: The height of the skewed tree is n (no. of elements) so the worst space complexity is O(N) and the height is (log N) for the balanced tree so the best space complexity is O(log N).