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;
}
Last modified 4yr ago