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


  • 0
    G

    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.