Simple C++ Inorder Traversal Code (Beats 86%)

  • 0

    Idea is to remember the last visited node in the in-order traversal and verify that it's value is less than the current node's value. Anytime this property breaks, it's not a valid BST.

        bool _isValidBST(TreeNode* root, TreeNode** prev) {
            if (!root) return true;
            if (!_isValidBST(root->left, prev)) return false;
            if (!(*prev)) *prev = root;
            else {
                if ((*prev)->val >= root->val) return false;
                *prev = root;
            return _isValidBST(root->right, prev);
        bool isValidBST(TreeNode* root) {
            TreeNode* prev = NULL;
            return _isValidBST(root, &prev);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.