#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
	bool isValidBST(TreeNode *root)
	{
		stack<TreeNode *> stk;
		int prev = INT_MIN;
		bool first = true;
		while (!stk.empty() || root != nullptr)
		{
			if (root != nullptr)
			{
				stk.push(root);
				root = root->left;
			}
			else
			{
				root = stk.top();
				stk.pop();
				if (!first && prev >= root->val)
				{
					return false;
				}
				first = false;
				prev = root->val;
				root = root->right;
			}
		}
		return true;
	}
};