> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/interview_questions/check-balanced.md).

# 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.

```cpp
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

```cpp
    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

```cpp
    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;
    }
```