how to solve this problem "Validate Binary Search Tree " iterative?

Question

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. LeetCode :validate binary search tree

This problem would be solved easily by using recursion. But, I wanna know how to use iteration to solve it. Thanks.

Answer 1

One way to solve it iteratively is to do an in-order traversal of the tree using explicit stack.

Then, as you traverses the tree, compare the previous node's value with the current node's value to verify all nodes' values follow a monotonically increasing order.

Better yet, you can design a BST iterator which yields a cleaner solution.

bool isBST(TreeNode *root) {
  BSTIterator iterator(root);
  int prev = INT_MIN;
  while (iterator.hasNext()) {
    int curr = iterator.next()->val;
    if (prev > curr) {
      return false;
    }
    prev = curr;
  }
  return true;
}

Answer 2

@1337c0d3r , I implement your algorithm. It works well if there is no duplicates.

  class Solution {
    class BSTIterator{
        stack<TreeNode *> s;
        void update(TreeNode *cur){
            while(cur){
                s.push(cur);
                cur = cur->left;
            }
        }
    public: 
        BSTIterator(TreeNode *root){
             update(root);
        }

        bool hasNext(){
            return !s.empty();
        }

        TreeNode* next(){
            if(!hasNext()) return NULL;
            TreeNode *t = s.top();
            s.pop();
            update(t->right);
            return t;
        }
    };
public:
    bool isValidBST(TreeNode *root) {
        BSTIterator iterator(root);
        int prev = INT_MIN;
        while (iterator.hasNext()) {
            int curr = iterator.next()->val;
            if (prev >= curr) {
                return false;
             }
             prev = curr;
        }
        return true;
    }
};