Tree traversals

Question

If the inorder traversal and preorder traversal of a binary tree having N elements are given, then what will be the time complexity of post order traversal and level order traversal of such a tree. Plz explain also ?

Answer 1

Time Complexity : O(n²). Worst case occurs when tree is skewed. 

Comments

@digvijay sir,

mine is also same

but answer is O(nlogn)

---

Sir could we go for the in-depth explanation of the above ques.

---

Worst case complexity always be O(n²). Average case complexity will be ⊝(nlogn).

Answer 2

when given binary tree postorder ,inorder or preorder , inorder then O(n^2)
when given binary search tree postorder ,inorder or preorder , inorder then O(nlogn)
O(nlogn) why because of sorted inorder.

Answer 3

If we assume that the constructed binary tree is always balanced, then we can guarantee the run time complexity to be O(Nlog N), where N is the number of nodes. However, this is not necessarily the case and the constructed binary tree can be skewed to the left/right, which has the worst complexity of O(N²).

ref: http://articles.leetcode.com/construct-binary-tree-from-inorder-and-preorder-postorder-traversal/