Calculation of Inorder Traversal Complexity I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research it is $O(n)$. Can you show it how come and my wrong?

void printInorder(Node node) 
    { 
        if (node == null)     // I think it is T(0) = 1
            return;           // constant c

        /* first recur on left child */
        printInorder(node.left);     // T(n-1)

        /* then print the data of node */
        System.out.print(node.key + " "); //constant(c)

        /* now recur on right child */
        printInorder(node.right); //T(n-1)
    }
In order to analyse the time complexity of a tree traversal you have to think in the terms of number of nodes visited. If a tree has $n$ nodes, then each node is visited only once in inorder traversal and hence the complexity is $O(n)$.

Here, the input is in terms of number of nodes in the tree and the hence the complexity.

The notion that each recursive call is $T(n-1)$ is wrong. Let say we have a tree that has three children to the left of root and three children to the right of root. So n = 7. Now when you visit root then you have two paths. One to left which has 3 children and one to right which also has 3 children. But $7-1 \neq 3$. Hence this notion of 2 recursive calls of $T(n-1)$ is wrong. 

It totally depends on the structure of the tree. In worst case a tree may degenerate to linked list  (a skew tree having children on only one side either left or right) and we know well that traversal of linked list is $O(n)$, for a list of n elements. Hence, also the worst case is $O(n)$.