Is This a Binary Search Tree?

  • + 3 comments

    You can just perform DFS and check if data is in ascending order. No additional data structures/parameters needed. Just one static variable (yep, I am a C programmer :))

    bool checkBST(Node* root) {
        static int last_visited = -2;
            if (!root) {
                return true;
            }
            if (!checkBST(root->left)) {
                return false;
            }
            if (root->data <= last_visited) {
                return false;
            }
            last_visited = root->data;
            if (!checkBST(root->right)) {
                return false;
            }
            return true;
    }
    
    • + 0 comments

      Great solution based on the constraints: 0 <= data <= 10^4. This is to utilize BST inorder traversal property. If the data can be min int, then the solution won't work.

    • + 0 comments

      This is a wonderful recursive solution.

    • + 0 comments

      Wow,,,, How could you tinker this method,, What a brilliant!