How to Validate Binary Search Tree in C/C++?

Given a binary tree root, return whether it’s a binary search tree. A binary tree node is a binary search tree if :

All nodes on its left subtree are smaller than node.val
All nodes on its right subtree are bigger than node.val
All nodes hold the these properties.
Constraint
n ≤ 100,000 where n is the number of nodes in root

Recursion

Binary Search Tree (BST) is a recursive data structure meaning that we can use recursion to check if its valid. However, we need to define a helper function that takes 3 parameters, the Root node, and the value ranges (min, max) for all the nodes in the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }
 
    bool isValidBST(TreeNode* root, long min, long max) {
        if (root == NULL) {
            return true;
        }
        return (root->val > min) && (root->val < max) &&
               isValidBST(root->left, min, root->val) && 
               isValidBST(root->right, root->val, max);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }

    bool isValidBST(TreeNode* root, long min, long max) {
        if (root == NULL) {
            return true;
        }
        return (root->val > min) && (root->val < max) &&
               isValidBST(root->left, min, root->val) && 
               isValidBST(root->right, root->val, max);
    }
};

Please note that there are no duplicate value, so the value range is a open region. Each time we check the node value to see if it falls in the range, then we recursively update the region and call the recursive function for left and right sub trees.

Iteration

The above recursion actually is a in-order traversal for BST trees, meaning that the left nodes (smaller) are visited first. The traversal will make a sorted array in non-descending order. If we use a Stack (First In Last Out) to store the current nodes and push its left nodes, check current node and then push the nodes in the right sub tree, we will have exactly the same order.

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

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        stack<TreeNode*> st;
        long min = LONG_MIN;
        while (!st.empty() || root) {
            if (root) { // if possible goes as left as possible
                st.push(root);
                root = root->left;
            } else {
                root = st.top();
                st.pop();
                if (root->val > min) {
                    min = root->val; // update the minimal
                } else {
                    return false;
                }
                root = root->right; // go right direction
            }
        }
        return true;
    }
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        stack<TreeNode*> st;
        long min = LONG_MIN;
        while (!st.empty() || root) {
            if (root) { // if possible goes as left as possible
                st.push(root);
                root = root->left;
            } else {
                root = st.top();
                st.pop();
                if (root->val > min) {
                    min = root->val; // update the minimal
                } else {
                    return false;
                }
                root = root->right; // go right direction
            }
        }
        return true;
    }
};

This is also the Depth First Search (DFS) where you go as deep (to the left sub trees) as possible, if it is a leaf node, then mark visited, rewind to the parent node (in-order, check the validity), and visit the right sub trees. So smaller nodes are visited first.

Algorithms to Validate a Binary Search Tree

• How to Validate Binary Search Tree in C/C++?
• Teaching Kids Programming – Recursive Algorithm to Validate a Binary Search Tree
• Teaching Kids Programming – Four Algorithms to Validate a Binary Search Tree

–EOF (The Ultimate Computing & Technology Blog) —