Iterative Method to check if the Binary Search Tree is valid

Problem Description:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Problem Analysis:

A valid BST always follows the left < root < right. The recursive way is check this rule is not broken. Think further to use iterative method, actually it is easy to find that this rule can be mapped to inorder traversal. Thus, the iterative method of in-order traversal of binary tree can be used to replace the recursive way. Here we just use the stack based algorithm. Time complexity is O(n). Morris Traversal is not used here.

However, there is a notice placed into the code. We set the pre_val initialized as INT_MIN. How about if the first value popped from the stack is exactly INT_MIN? In this case, the curr_val used to compare the pre_val  will lead to a incorrect conclusion that the BST is invalid. To avoid this corner case, we add a flag first_compare and initialized as 1 indicating it is still in the first compare. Thus during the first compare, if curr_val with vale of INT_MIN will not lead to return false. Once the first compare is finished, first_compare is set to 0.

Code is here and is accepted in leetcode.

/**
 * 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) {
        if(!root) return true;

        stack<TreeNode*> S;
        TreeNode* current = root;
        int curr_val, pre_val = INT_MIN;
        int first_compare = 1; //in first compare.

        while(!S.empty() || current){
            if(current){
                S.push(current);
                current = current->left;
            }
            else{
                current = S.top();
                curr_val = current->val;
                if(curr_val <= pre_val && first_compare == 0){
                    return false;
                }
                first_compare = 0; //after first compare
                pre_val = curr_val;
                S.pop();
                current = current->right;
            }
        }
     return true;
     }
};
Advertisements
This entry was posted in Algorithms. Bookmark the permalink.

Welcome your comments!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s