Check Balanced

4.4 Check Balanced: Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

• Brainstorm:

  • Reminded me of a post order traversal, where we recursively access individual subtrees, starting with the left.

bool checkBalance(TreeNode *root) {
    return checkBalance(Treenode *root) != INT_MIN;
}

int checkBalance(TreeNode *root) {
    if (root == nullptr) return -1;

    int left = checkBalance(root->left);
    if (left == INT_MIN) return INT_MIN;
    int right = checkBalance(root->right);
    if (right == INT_MIN) return INT_MIN;

    if (abs(left - right) >= 2) {
        return INT_MIN;
    }
    else {
        return max(left, right) + 1;
    }
}

4.5 Validate BST: Implement a function to check if a binary tree is a binary search tree.

• We can validate it through an inorder traversal

• O(2n) time and space

    bool isBST(Node *root, vector<int> &ar) {
        if (root) {
            isBST(root->left, ar);
            ar.push_back(root->value);
            isBST(root->right, ar);
        }
        return is_sorted(ar.begin(), ar.end());
    }

• We can speed things up a little by just checking the previous element as we go along

• O(n) time and space

    int prev = INT_MIN;
    bool isBST2(Node *root) {
        if (root) {
            isBST2(root->left);
            if (prev > root->value) {
                return false;
            }
            prev = root->value;
            isBST2(root->right);
        }
        return true;
    }