解释为什么该二叉树的遍历算法有O（NlogN）的时间复杂度？

我要通过破解编码面试书，现在我正在做一个二叉树的锻炼。还有就是根据书的代码片段O(NlogN)，但是，我不明白这是为什么。我可以理解，如果该算法是O(N)，但我不知道那里的logN是从他们的分析中来。

int getHeight(TreeNode root) {
    if (root == null) return -1; // Base case
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

boolean isBalanced(TreeNode root) {
    if (root == null) return true; // Base case

    int heightDiff = getHeight(root.left) - getHeight(root.right);
    if (Math.abs(heightDiff) > 1) {
        return false;
    } else { 
        // Recurse
        return isBalanced(root.left) && isBalanced(root.right);
    }
}