Proving time complexity for recursive function-CodePudding

How would I prove that the time complexity of this algorithm that finds the depth of a binary tree is O(N) where N is the number of nodes? I understand the reasoning why this is true, since the algorithm checks each node once, but I'm not sure how I would mathematically prove this. Thanks!

private static int depth(TreeNode node){
    if(node == null){
        return 0;
    }

    int leftDepth = depth(node.left);
    int rightDepth = depth(node.right);

    return 1   Math.max(leftDepth, rightDepth);
}

CodePudding user response：

Let's assume that we visited any of the vertices 2 times. This means that there is an edge from the current vertex to the vertex that we have already visited, that is, we have found a cycle in the tree-a contradiction. So, we visit each vertex only once, hence the complexity of the algorithm is O (n).

CodePudding user response：

You are traversing both branches of every node, so you will visit each node exactly once, which itself is O(n).

The operation of traversing from one node to another is constant time.

Overall, you have O(n) operations each costing O(1), so your algorithm is O(n).