leetcode_validate-binary-search-tree

algorithm
C++, algorithm, array, leetcode

leetcode problem solving

https://leetcode.com/problems/validate-binary-search-tree/

Following two solutions are simple to solve this problem.

  • Solution A. BST should maintain the following features.

    1. for any node, all values of nodes in the left subtree should be smaller than the node.
    2. for any node, all values of nodes in the right subtree should be bigger than the node.

  • Solution B. if the tree accepted following features,

    1. the maximum value of the left subtree is smaller than the parent node.
    2. the minimum value of the right subtree is bigger than the parent node.

Solution A is the key idea of latter solution with child comparison.
Solution B is the key idea of former solution with root comparison.

Here’s my C++ implementations of the solutions.

Min / Max validation with root comparison O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// ======================= Root comparison approach ============================
class BSTinfo{
public:
  bool isValid;
  int maxVal;
  int minVal;
  BSTinfo(bool is, int minV, int maxV) : isValid(is), maxVal(maxV), minVal(minV){};
};
BSTinfo isValidBSTinfo(TreeNode* root){
  // 00. edge & base cases
  if (root == nullptr)
    return BSTinfo(true, -1, -1);
  if (root->left == nullptr && root->right == nullptr)
    return BSTinfo(true, root->val, root->val);
  // 01. in case one subtree is a leaf node
  if (root->left == nullptr){
    BSTinfo rInfo = isValidBSTinfo(root->right);
    if (rInfo.isValid && root->val < rInfo.minVal)
      return BSTinfo(true, root->val, rInfo.maxVal);
    return BSTinfo(false, -1, -1);
  }
  if (root->right == nullptr){
    BSTinfo lInfo = isValidBSTinfo(root->left);
    if (lInfo.isValid && lInfo.maxVal < root->val)
      return BSTinfo(true, lInfo.minVal, root->val);
    return BSTinfo(false, -1, -1);
  }
  // 02. other cases
  BSTinfo lInfo = isValidBSTinfo(root->left);
  BSTinfo rInfo = isValidBSTinfo(root->right);
  if (lInfo.isValid && rInfo.isValid){
    if (lInfo.maxVal < root->val && root->val < rInfo.minVal)
      return BSTinfo(true, lInfo.minVal, rInfo.maxVal);
  }
  return BSTinfo(false, -1, -1);
}
bool isValidBST(TreeNode* root) {
    return isValidBSTinfo(root).isValid;
}

Min / Max validation with child comparison O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ======================= Child comparison approach ===========================
bool isValidBST_(TreeNode* pNode, TreeNode* minNode, TreeNode* maxNode){
  // 00. base case
  if (pNode == nullptr)
    return true;
  // 01. edge cases : in case one subtree is invalid
  bool isLeftInvalid = minNode && minNode->val >= pNode->val;
  bool isRightInvalid = maxNode && maxNode->val <= pNode->val;
  if (isLeftInvalid || isRightInvalid)
    return false;
  // 02. other cases
  bool isLeftValid = isValidBST_(pNode->left, minNode, pNode);
  bool isRightValid = isValidBST_(pNode->right, pNode, maxNode);
  return isLeftValid && isRightValid;
}
bool isValidBST(TreeNode* root) {
    return isValidBST_(root, nullptr, nullptr);
}
Share Comments