Validate Binary Search Tree

class Solution {
public:
    bool isBinarySearchTree(TreeNode* node) {
        stack<TreeNode*> nodeStack;
        TreeNode* lastNode = nullptr;
    
        while (!nodeStack.empty() or node != nullptr) {
            while (node != nullptr) {
                nodeStack.push(node);
                node = node->left;
            }
            node = nodeStack.top();
            nodeStack.pop();
    
            if (lastNode != nullptr and node->val <= lastNode->val) {
                return false;
            }
            lastNode = node;
            node = node->right;
        }
        return true;
    }
};

The provided C++ code defines a method to validate whether a binary tree is a binary search tree (BST). It employs an iterative approach using a stack to traverse the tree in an inorder sequence, ensuring that each node's value is greater than the previous node's value, which is a fundamental property of BSTs.

Here’s a quick overview of how the code achieves this:

• Initialize an empty stack to keep track of nodes and a pointer lastNode set to nullptr to store the last visited node during the traversal.

• Use a while loop to continue the process until you have visited all nodes. Inside this loop, another while loop pushes all left children of the current node onto the stack until a null is found.

• After reaching the leftmost node, pop the top node from the stack to process it. This node is stored in node, and then its value is compared to the value of lastNode. If node->val is not greater than lastNode->val, the function returns false, indicating that the tree is not a BST.

• Set lastNode to the current node and then move to the right child of the node.

• If the entire tree is correctly traversed without finding any violations of the BST properties, return true.

The use of a stack and the non-recursive approach makes this method space-efficient, particularly for trees with large heights. The algorithm ensures that each node is checked precisely once in its inorder sequence, keeping the time complexity in check.

class Solution {
    public boolean checkValidBST(TreeNode node) {
        Deque<TreeNode> nodes = new LinkedList<>();
        Integer last = null;
    
        while (!nodes.isEmpty() || node != null) {
            while (node != null) {
                nodes.push(node);
                node = node.left;
            }
            node = nodes.pop();
    
            if (last != null && node.val <= last) {
                return false;
            }
            last = node.val;
            node = node.right;
        }
        return true;
    }
}

In this solution, you validate if a given binary tree is a binary search tree (BST) using an in-order traversal approach in Java. The method checkValidBST is designed to traverse the tree and ensure that values are in strictly increasing order, which is a key property of BSTs.

• Begin by creating an instance of Deque<TreeNode> to keep track of the nodes as you traverse. Deque is utilized instead of a standard stack for its flexibility in insertion and deletion.

• Initialize an Integer variable last to store the value of the last visited node. This variable helps in comparison with the current node's value to make sure the BST property holds.

• Utilize two nested while loops:

  • The outer loop continues until all nodes are processed either from the stack or directly from the tree.
  • The inner loop deals with moving to the leftmost node, pushing each node onto the stack as you progress.

• After reaching the leftmost node, pop elements from the stack (which gives you the inorder sequence).

  • If the last is not null and the current node's value is less than or equal to last, the tree is not a BST. Return false.
  • Update last to the current node.val.

• Then move to the right child of the node and repeat the process.

• If the entire tree satisfies the BST conditions, return true after all nodes have been correctly processed.

This approach ensures that each element is checked through its inorder traversal, maintaining an efficiency that requires O(n) time and O(n) space complexities, where n is the number of nodes in the tree.

bool checkBST(struct TreeNode* node) {
    struct TreeNode* nodeStack[1000];
    struct TreeNode* last = NULL;
    int stackIndex = -1;
    while (node != NULL || stackIndex >= 0) {
        while (node != NULL) {
            nodeStack[++stackIndex] = node;
            node = node->left;
        }
        node = nodeStack[stackIndex--];
        if (last != NULL && node->val <= last->val) {
            return false;
        }
        last = node;
        node = node->right;
    }
    return true;
}

The problem involves verifying whether a given binary tree is a valid Binary Search Tree (BST). The C language solution employs an iterative approach using a stack to perform an in-order traversal of the tree, ensuring that the values of the nodes meet the properties of a BST.

• A structure TreeNode represents each node of the tree.
• An array nodeStack replicates the functionality of a stack, storing nodes of the tree.
• The stackIndex keeps track of the position on the top of the stack.
• A pointer last references the last node visited during the in-order traversal.

The solution follows these steps:

1. Traverse the left subtree by pushing all nodes onto the stack.
2. Upon reaching a null node, step back to handle the node on the top of the stack, checking the order property.
3. Compare the current node's value with last node's value (value of the last processed node). If the current node's value is less or equal to last's value, it indicates an invalid BST structure, hence return false.
4. Update the last pointer to the current node and move to the right subtree.
5. Repeat the traversal until all nodes are processed. If no violations of the BST properties are found, return true.

Using a stack and maintaining a pointer to the last visited node facilitates an effective in-order traversal and comparison without recursion. This ensures that each node is visited in the correct order and compared effectively to uphold the strict ordering property of BSTs.

var checkValidBST = function (node) {
    let nodeStack = [];
    let previous = null;
    while (nodeStack.length !== 0 || node !== null) {
        while (node !== null) {
            nodeStack.push(node);
            node = node.left;
        }
        node = nodeStack.pop();
        if (previous !== null && node.val <= previous) {
            return false;
        }
        previous = node.val;
        node = node.right;
    }
    return true;
};

This JavaScript solution implements a function to check if a given binary tree is a valid Binary Search Tree (BST). The function, checkValidBST, uses an in-order traversal approach which is common for this kind of validation because it leverages the BST property that values must be in ascending order if traversed in-order.

Here is a breakdown of how the code ensures the BST is valid:

• Initialize nodeStack to keep track of nodes and previous to store the value of the last visited node.
• Use a while loop to traverse the tree. The outer loop continues until there are no nodes left to visit.
• The inner loop explores the leftmost path of the current subtree, pushing each node onto the stack until a null node is found.
• Node retrieval occurs by popping the top node from the stack.
• After retrieving a node, it checks if the current node's value is less than or equal to the previous node's value. If true, it violates the BST properties and returns false.
• previous gets updated to the current node's value, and the traversal moves to the right subtree.

By following the in-order traversal and checking the order of node values carefully, this function efficiently verifies the integrity of the BST. Ensure that this approach is applied to a tree structure that specifically follows the definition and conventions of a binary search tree for correct results.

class Solution:
    def check_bst(self, node: TreeNode) -> bool:
        nodes_stack, last_value = [], float('-inf')
    
        while nodes_stack or node:
            while node:
                nodes_stack.append(node)
                node = node.left
            node = nodes_stack.pop()
    
            if node.val <= last_value:
                return False
            last_value = node.val
            node = node.right
    
        return True

The provided Python code defines a method to validate whether a binary tree is a binary search tree (BST). Here's an overview of how the solution works:

• A function check_bst is defined, which accepts a node, assumed to be the root of a binary tree.

• Two variables are initialized:

  • nodes_stack to keep track of the tree nodes as the tree is traversed.
  • last_value initialized to negative infinity to hold the last node value processed, aiding in comparison.

• The function uses an iterative in-order traversal to process each node of the tree. The in-order traversal ensures nodes are visited in a non-decreasing order if the tree is a BST.

• During the traversal:

  • Nodes are repeatedly added to nodes_stack until the leftmost node is reached.
  • Nodes are then popped from nodes_stack for processing.
  • For each node processed, the function checks if the node's value is less than or equal to the last_value. If true, the tree is not a BST and False is returned.
  • If a node passes the check, last_value is updated to the current node's value, and traversal continues to the right child.

• If all nodes maintain the BST property, the function returns True after all nodes have been processed, confirming the tree is a valid BST.

This approach efficiently validates the BST properties using an iterative technique, ensuring minimal space usage and adhering to BST principles by checking the order of node values during in-order traversal.