BST or NOT ??

Is it a Binary Search Tree (BST)?

To determine if a given binary tree is a Binary Search Tree (BST), we need to check if the elements in the tree are arranged in a specific order. In a BST, the left child of a node should be less than the node itself, and the right child should be greater than the node.

To validate if a binary tree is a BST, we can perform an in-order traversal of the tree and check if the elements are in ascending order. If they are, then the tree is a BST.

Here are the steps to determine if a binary tree is a BST:

1. Perform an in-order traversal of the binary tree.
2. Keep track of the previously visited node during the traversal.
3. At each node, compare the value of the current node with the previously visited node.
4. If the value of the current node is less than or equal to the previously visited node, the tree is not a BST.
5. If the value of the current node is greater than the previously visited node, continue the traversal.
6. If the traversal completes without any violations, the tree is a BST.

Let's go through an example to illustrate this process:

Consider the following binary tree:

        5
       / \
      3   7
     / \   \
    2   4   8

Performing an in-order traversal of this tree would give us the sequence: 2, 3, 4, 5, 7, 8. Since the elements are in ascending order, we can conclude that this binary tree is a BST.

Now, let's consider another binary tree:

        5
       / \
      3   7
     / \   \
    2   6   8

Performing an in-order traversal of this tree would give us the sequence: 2, 3, 6, 5, 7, 8. In this case, the element 6 violates the BST property since it is greater than its parent node (3). Therefore, this binary tree is not a BST.

In summary, to determine if a binary tree is a BST, we can perform an in-order traversal and check if the elements are in ascending order. If they are, the tree is a BST. Otherwise, it is not.

[2]