Validate if Tree is BST in DSA C++

Mental Model

A binary search tree (BST) is a tree where every node's left child is smaller and right child is bigger than the node itself. We check this by making sure all nodes follow this rule in the whole tree.

Analogy: Imagine a family tree where every child on the left side is younger than their parent, and every child on the right side is older. To confirm it's a proper family tree, you check each parent and their children follow this age rule.

      5
     / \
    3   7
   / \   \
  2   4   8

(Each left child < parent < right child)

Dry Run Walkthrough

Input: Tree: 5 with left child 3 and right child 7; 3 has children 2 and 4; 7 has right child 8

Goal: Check if this tree follows BST rules everywhere

Step 1: Start at root node 5 with allowed range (-∞, +∞)

Node=5, Range=(-∞, +∞)

Why: We begin checking from the root with no limits

Step 2: Check left child 3 with range (-∞, 5)

Node=3, Range=(-∞, 5)

Why: Left child must be less than 5

Step 3: Check left child of 3: node 2 with range (-∞, 3)

Node=2, Range=(-∞, 3)

Why: Left child of 3 must be less than 3

Step 4: Node 2 has no children, return true

Leaf node 2 validated

Why: Leaf nodes are valid by default

Step 5: Check right child of 3: node 4 with range (3, 5)

Node=4, Range=(3, 5)

Why: Right child of 3 must be greater than 3 and less than 5

Step 6: Node 4 has no children, return true

Leaf node 4 validated

Why: Leaf nodes are valid by default

Step 7: Check right child 7 of root 5 with range (5, +∞)

Node=7, Range=(5, +∞)

Why: Right child must be greater than 5

Step 8: Check right child of 7: node 8 with range (7, +∞)

Node=8, Range=(7, +∞)

Why: Right child of 7 must be greater than 7

Step 9: Node 8 has no children, return true

Leaf node 8 validated

Why: Leaf nodes are valid by default

Step 10: All nodes validated, tree is BST

5 -> 3 -> 2,4 and 7 -> 8 all valid

Why: Every node respects BST rules

Result:

5 -> 3 -> 2,4 and 7 -> 8 all valid
Tree is a BST: true

Annotated Code

DSA C++

#include <iostream>
#include <limits>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

bool isBSTUtil(Node* node, long long minVal, long long maxVal) {
    if (node == nullptr) return true; // empty node is valid
    if (node->val <= minVal || node->val >= maxVal) return false; // violates BST range
    // check left subtree with updated max
    if (!isBSTUtil(node->left, minVal, node->val)) return false;
    // check right subtree with updated min
    if (!isBSTUtil(node->right, node->val, maxVal)) return false;
    return true; // current node valid and subtrees valid
}

bool isBST(Node* root) {
    return isBSTUtil(root, LLONG_MIN, LLONG_MAX);
}

int main() {
    // Construct tree:
    //       5
    //      / \
    //     3   7
    //    / \   \
    //   2   4   8
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(7);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->right->right = new Node(8);

    cout << boolalpha << isBST(root) << endl;
    return 0;
}

if (node == nullptr) return true; // empty node is valid

base case: empty subtree is valid BST

if (node->val <= minVal || node->val >= maxVal) return false; // violates BST range

check current node value against allowed min and max range

if (!isBSTUtil(node->left, minVal, node->val)) return false;

recursively check left subtree with updated max limit

if (!isBSTUtil(node->right, node->val, maxVal)) return false;

recursively check right subtree with updated min limit

return true; // current node valid and subtrees valid

all checks passed, subtree is BST

Output

true

Complexity Analysis

Time: O(n) because we visit each node once to check BST property

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to naive approach checking each node's subtree for min/max values repeatedly (O(n^2)), this method is efficient by passing range limits down the tree

Edge Cases

Empty tree (root is nullptr)

Returns true since empty tree is a valid BST

DSA C++

if (node == nullptr) return true; // empty node is valid

Single node tree

Returns true as single node satisfies BST property

DSA C++

if (node == nullptr) return true; // empty node is valid

Tree with duplicate values

Returns false because duplicates violate strict BST property (<= or >= not allowed)

DSA C++

if (node->val <= minVal || node->val >= maxVal) return false; // violates BST range

When to Use This Pattern

When you need to confirm if a binary tree follows the BST rules, use the range-checking pattern that passes min and max limits down the tree to validate each node.

Common Mistakes

Mistake: Only checking immediate children values without considering entire subtree ranges
Fix: Pass down min and max allowed values to each recursive call to ensure all descendants respect BST property

Mistake: Allowing duplicates by using < or > instead of <= or >= in comparisons
Fix: Use strict inequalities (node->val <= minVal or node->val >= maxVal) to disallow duplicates

Summary

Checks if a binary tree is a valid binary search tree by verifying node values fall within allowed ranges.

Use when you need to confirm the BST property for a given binary tree structure.

The key insight is to track and update the allowed min and max value range for each node during traversal.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. Every node has exactly two children.

B. For every node, all nodes in the left subtree are smaller and all nodes in the right subtree are larger.

C. All leaf nodes are at the same depth.

D. The tree is perfectly balanced.

Solution

1. Step 1: Understand BST property

   A BST requires that for each node, values in the left subtree are smaller and values in the right subtree are larger.

2. Step 2: Compare other options

   Options B, C, and D describe other tree properties but not BST specifically.

3. Final Answer:

   For every node, all nodes in the left subtree are smaller and all nodes in the right subtree are larger. -> Option B

4. Quick Check:

   BST property = left < node < right [OK]

Hint: Remember BST means left < node < right for all nodes [OK]

Common Mistakes:

• Confusing BST with balanced tree
• Thinking all nodes must have two children
• Assuming leaf nodes must be at same depth

2. Which of the following C++ function signatures is correct to check if a binary tree is a BST using min and max limits?

easy

A. bool isBST(Node* root, int min, int max);

B. bool isBST(Node root, int min, int max);

C. bool isBST(Node* root, int min);

D. bool isBST(Node root);

Solution

1. Step 1: Check parameter types

   To check BST, we need a pointer to the root node and min/max limits to validate node values.

2. Step 2: Validate function signature

   bool isBST(Node* root, int min, int max); uses Node* root and both min and max parameters, which is correct for BST validation.

3. Final Answer:

   bool isBST(Node* root, int min, int max); -> Option A

4. Quick Check:

   Use pointer and min/max for BST check [OK]

Hint: Use pointer and min/max parameters for BST validation [OK]

Common Mistakes:

• Passing Node by value instead of pointer
• Missing max parameter
• Using incorrect parameter types

3. What will be the output of the following code snippet?

#include <iostream>
#include <climits>

struct Node {
  int data;
  Node* left;
  Node* right;
};

bool isBSTUtil(Node* root, int min, int max) {
  if (!root) return true;
  if (root->data <= min || root->data >= max) return false;
  return isBSTUtil(root->left, min, root->data) && isBSTUtil(root->right, root->data, max);
}

bool isBST(Node* root) {
  return isBSTUtil(root, INT_MIN, INT_MAX);
}

int main() {
  Node n1 = {10, nullptr, nullptr};
  Node n2 = {5, nullptr, nullptr};
  Node n3 = {15, nullptr, nullptr};
  n1.left = &n2;
  n1.right = &n3;
  std::cout << (isBST(&n1) ? "Yes" : "No") << std::endl;
  return 0;
}

medium

A. Runtime error

B. No

C. Compilation error

D. Yes

Solution

1. Step 1: Analyze tree structure

   Root is 10, left child 5 < 10, right child 15 > 10, so BST property holds.

2. Step 2: Check BST validation function

   Function correctly checks node values within min and max limits recursively.

3. Final Answer:

   Yes -> Option D

4. Quick Check:

   Tree satisfies BST rules = Yes [OK]

Hint: Check left < root < right for all nodes [OK]

Common Mistakes:

• Confusing <= and < in comparisons
• Not passing correct min/max values
• Ignoring nullptr base case

4. Identify the bug in this BST validation code snippet:

bool isBSTUtil(Node* root, int min, int max) {
  if (!root) return true;
  if (root->data < min || root->data > max) return false;
  return isBSTUtil(root->left, min, root->data) && isBSTUtil(root->right, root->data, max);
}

medium

A. The function should not use recursion.

B. The base case should return false when root is nullptr.

C. The comparison should use <= min and >= max to exclude equal values.

D. The min and max parameters should be swapped in recursive calls.

Solution

1. Step 1: Check comparison operators

   BST requires strict inequality: node values must be greater than min and less than max, so use <= and >= to reject equal values.

2. Step 2: Validate base case and recursion

   Base case returning true for nullptr is correct; recursion is necessary; min and max parameters are correctly passed.

3. Final Answer:

   The comparison should use <= min and >= max to exclude equal values. -> Option C

4. Quick Check:

   Use strict inequalities to validate BST [OK]

Hint: Use <= and >= to reject duplicates in BST check [OK]

Common Mistakes:

• Allowing equal values breaks BST property
• Returning false on nullptr causes errors
• Swapping min and max in recursion

5. Given a binary tree where nodes can have duplicate values, how would you modify the BST validation function to allow duplicates only on the right subtree?

hard

A. Allow duplicates on right subtree by changing left subtree check to root->data < min and right subtree check to root->data >= max.

B. Change the left subtree check to root->data <= min and right subtree check to root->data > max.

C. Allow duplicates on left subtree by changing comparison to root->data <= min.

D. Disallow duplicates completely by using strict inequalities everywhere.

Solution

1. Step 1: Understand duplicate placement rule

   Duplicates allowed only on right subtree means left subtree nodes must be strictly less than root.

2. Step 2: Adjust comparison operators

   Left subtree check uses < min (strict), right subtree check uses >= max (allow equal or greater).

3. Final Answer:

   Allow duplicates on right subtree by changing left subtree check to root->data < min and right subtree check to root->data >= max. -> Option A

4. Quick Check:

   Duplicates only right = left < root, right >= root [OK]

Hint: Allow duplicates on right by using >= in right subtree check [OK]

Common Mistakes:

• Allowing duplicates on left subtree incorrectly
• Using <= on left subtree allowing duplicates there
• Not adjusting comparisons for duplicates