DFS | Easy Solution | C++

interview-questions
programming
Tags: #<Tag:0x00007f242436ee68> #<Tag:0x00007f242436ecd8>

#1

The approach for this is to check for every node whether the height difference between the left subtree and right subtree of node is at most 1.

We will be using post order traversal to check for each node and if it is satisfied for both the left child and right child, we will check for root. We will be using height for purpose of checking, and not depth of node.
The height of a particular node would be 0 if it is null, A leaf node is at height 1. The height of a inner node is 1 + max(height_left, height_right).

Code
int dfs(TreeNode* root, bool &valid){
    if(!valid)
        return 0;

    if(root == nullptr)
        return 0;
    
    int h_l = dfs(root -> left, valid);
    int h_r = dfs(root -> right, valid);

    if(abs(h_l - h_r) > 1)
        valid = false;

    return 1 + max(h_l, h_r);
}

int Solution::isBalanced(TreeNode* A) {
    bool valid = true;
    dfs(A, valid);
    return valid;
}

The time complexity is O(n) and Space Complexity is O(1)