It is leetcode problem 94. Binary Tree inorder traversal.

       /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null)
            return list;
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);

        return list;
    }
}

I am not sure, but space complexity : O(1)? time complextity O(n)? because I am visiting each and every nodes at least once?

Usually what I do, if there's loop --> O(n), nested loop-->O(n^2), but I don't really sure how to calculate space complexity and time complexity in recursion. Could you help me with this concept please?

Thank you

CodePudding user response：

Time complexity

If we ignore the recursive calls, the time complexity for executing inOrderTraversal is θ(1): all the steps in the code, except the recursive calls, have Θ(1) complexity. Given that the graph is a tree, inOrderTraversal is called exactly once on each node, and on all null references. In a tree, the number of null references is equal to the number of nodes in the tree plus 1. So if the tree has