C++ in-order traversal, and please do not rely on buggy INT_MAX, INT_MIN solutions any more


  • 188
    J
    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            TreeNode* prev = NULL;
            return validate(root, prev);
        }
        bool validate(TreeNode* node, TreeNode* &prev) {
            if (node == NULL) return true;
            if (!validate(node->left, prev)) return false;
            if (prev != NULL && prev->val >= node->val) return false;
            prev = node;
            return validate(node->right, prev);
        }
    };
    

    Update:

    If we use in-order traversal to serialize a binary search tree, we can
    get a list of values in ascending order. It can be proved with the
    definition of BST. And here I use the reference of TreeNode
    pointer prev as a global variable to mark the address of previous node in the
    list.

    “In-order Traversal”:
    https://en.wikipedia.org/wiki/Tree_traversal#In-order

    If you know what INT_MAX or INT_MIN is, then it is no excuse for your carelessness.


  • 2
    J

    Can you explain your logic?


  • 2
    J

    If we use in-order traversal to serialize a binary search tree, we can get a list of values in ascending order. It can be proved with the definition of BST. And here I use the reference of TreeNode pointer prev as a global variable to mark the address of previous node in the list.

    “In-order Traversal”: https://en.wikipedia.org/wiki/Tree_traversal#In-order


  • 0
    J

    Got it! great idea!


  • 0
    T

    Same idea to you, and got 2 mistake :)

    1. Static variable
    2. Rely on INT_MIN
    class Solution {
    public:
        bool isValidBST(TreeNode *root) {
            static int m = INT_MIN;
            if(root == NULL) return true;
            if(!isValidBST(root->left)) return false;
            if(!(root->val > m)) {
                return false;
            }
            m = root->val;
            return isValidBST(root->right);
        }
    };
    

    But still can rely on LLONG_MIN


  • 0
    J

    It's good to use static variable if it is just a small object and the function is not a lambda function. Using reference variables is just another way to avoid using global variables.

    You can use another static variable to eliminate the INT_MIN problem. ;-) like static bool first = false;


  • 1
    T

    No, can not use static variable here. The behavior of static variable in method is similar to class static member, just init once, and all objects share the value. The code will fail in multiple test.


  • 0
    J

    You are right. I forgot it was a class method. :p


  • 0
    M

    solution of insight !


  • 5
    A

    In java

    TreeNode invalidNode = new TreeNode(Integer.MAX_VALUE);
    
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null) != invalidNode;
    }
    
    public TreeNode isValidBST(TreeNode node, TreeNode prev) {
        if( node == null ) return prev;
        prev = isValidBST(node.left, prev);
        if( prev != null && node.val <= prev.val ) return invalidNode;
        return isValidBST(node.right, node);
    }

  • 8
    N

    Why rely on LLONG_MIN? Don't you think if you are in a true interview, the next question the interviewer will ask, "okay I have changed my input type to long" then? I am sorry but using long limit to such question is like taking shortcut to just get your answer accepted and won't help you in real interview.


  • 1
    R

    great idea! it really inspire me a lot.
    in C solution

    bool in_order_validBST(struct TreeNode* node,struct TreeNode** prev) {
    	if(NULL==node) return true;
        
    	if(!in_order_validBST(node->left,prev)) return false;
    	if(NULL!=(*prev) && (*prev)->val>= node->val) return false;
    
    	*prev=node;
    
    	return in_order_validBST(node->right,prev);
    }
    
    bool isValidBST(struct TreeNode* root) {
    
    	struct TreeNode *ptmp=NULL;
    	return in_order_validBST(root,&ptmp);
    }

  • 0
    E

    Yeah, it's really important to remember we are practicing for real interview. Thank you for your remind.


  • 0
    L

    OK. just checked INT_MIN. quite small.


  • 0
    G

    In isValidBST(), when validate() is invoked for the first time, NULL is passed to the second parameter of isValidBST(), which requires a reference. As a reference to NULL is an undefined behavior in the C++ standard, is it better to use pointer-to-pointer instead of reference-to-pointer?


  • 0
    G

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


  • 0
    J

    They are the same. I'm using a reference to prev, not to NULL.


  • 0
    E

    Very concise and elegant.


  • 0
    Q

    Why use reference for the prev in the recursion function?


  • 0
    W

    very briliant


Log in to reply
 

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