Time complexity of construction of a binary tree from inorder and preorder traversals

Question

Given Here is the code for constructing a tree from the inorder and preorder traversals. I cant figure out how they arrived at an O(n^2) time complexity. Any ideas? I see that the search for an index in the inorder sequence would be O(n), how is the rest of it computed?

Answer 1

The O(N^2) complexity results from the fact that for every item in the Preorder traversal (of which there are N), you have to search for its partition in the Inorder traversal, (again there are N of these).

Roughly speaking, you can consider this algorithm as placing the nodes on a grid, where the Inorder traversal provides the x co-ordinates and the Preorder traversal provides the y co-ordinates:

Take the example they gave, with the following traversals (Inorder then Preorder):

Inorder: DBEAFC
Preorder: ABDECF

Now this is the grid they are being put on:

     D    B    E    A    F    C
A    +    +    +    A    |    |
     |    +--------------+    |
B|F  +    B    |         F    |
     +---------+         -----+
DE|C D         E              C

Now, the algorithm needs to know where in the grid to place each node, which it does simply by putting the node at the position in the grid where the x and y co-ordinates are the same.

It looks as though the size of the grid is actually NlogN in this case, which would result in an NlogN complexity for traversing the grid (and so an NlogN time complexity for the algorithm) but this tree is balanced. In the worst case, your tree might in fact be a linked list.

E.g. consider this tree, where the preorder and inorder traversals are the same:

Inorder: DBEAFC
Preorder: DBEAFC

     D    B    E    A    F    C
D    D    |    |    |    |    |
     -----+    |    |    |    |
B         B    |    |    |    |
          -----+    |    |    |
E              E    |    |    |
               -----+    |    |
A                   A    |    |
                    -----+    | 
F                        F    |
                         -----+
C                             C

This is the worst case, and you see, the grid has N*N positions in it to check. So in the worst case, there is an N*N time complexity.