Given a binary tree, determine if it is height-balanced(difference in depth is not mroe than 1) (leetcode 110)

Question

While learning to solve this, i came across 2 solutions and i cannot understand their time complexities, please teach me how to do so.

Sol 1: O(n) - Postorder DFS to find the height of every node

var isBalanced = function(root) {

let dfs = function(node) {
    if (!node) return 0;
    let left = 1 + dfs(node.left);
    let right = 1 + dfs(node.right);
    if (Math.abs(left - right) > 1) return Infinity;
    return Math.max(left, right);
}

return dfs(root)==Infinity?false:true;
};

Sol 2: O(n^2)- Standard Top-Down recursion

var isBalanced = function(root) {
if (!root) return true;

let height = function(node) {
    if (!node) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

return Math.abs(height(root.left) - height(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right);
 };

Answer 1

You have to ask yourself how many nodes your algorithm visits.

Solution 1 is a depth-first-search, which visits each node exactly once. The rest are constant-time operations. Therefore, if you have n nodes in your tree, the complexity is O(n).

Solution 2 is visiting each node, but for each visit, it visits each of its child nodes. Therefore, the complexity is O(n * n) = O(n²).