Check if a tree is a Binary Search Tree or Binary Tree

Problem Statement: Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.

Both the left and right subtrees must also be binary search trees.

Examples

Example 1:

Input Format

Tree: 5 1 6 -1 -1 4 8

Output: False, Not a BST

Explanation

Node with value 4 is present in the right subtree of the root node with value 5. This violates the property of the binary search tree that the right subtree should only contain nodes with values greater than a node.

Example 2:

Input Format: 

Tree: 13 10 15 7 12 14 17 -1 9 -1 -1 -1 -1 16 -1 8 -1 -1 -1

Output: True, the given tree is a BST.

Explanation:

All nodes are following the property of BST that for each node, all nodes in its left subtree have values smaller and all nodes in its right subtree have values greater than the current node’s value.

Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution:

Approach: 

In a Binary Search Tree (BST), every node holds a value, and the left subtree of a node contains values smaller than that node’s value, while the right subtree holds values greater than the node’s value. To ensure the entire tree follows this rule, we establish a range of valid values for each node.

For any given node, its left subtree should contain values within a range from the smallest possible value up to just below the node’s value. Similarly, the right subtree’s values should fall within a range from just above the node’s value up to the largest possible value. This range checking ensures that at every step, each node’s value complies with the order established by a BST.

Algorithm:

Step 1: Start at the root of the binary tree and define a recursive function isValidBST that takes a node, along with its minimum and maximum allowed values as arguments.

  • If the node is null, return true as that would be a valid BST.
  • If the node’s value is outside the given range (smaller than the min value or greater than the max value), return false.

Step 2: Call the isValidBST function starting from the root node with an initial range of minimum and maximum values that cover the full range of possible values (negative int min to positive int max). If the function returns true, the tree is a valid BST; otherwise, it’s not.

Step 3: Recursively call isValidBST for each node by updating the maximum allowed value for the left subtree to be less than the current node’s value and updating the minimum allowed value for the right subtree to be more than the current node’s value.

Code:

C++ Code

#include <iostream>
#include <climits>
using namespace std;

// Definition of TreeNode structure
// for a binary tree node
struct TreeNode {
    // Value of the node
    int val;    
    
    // Pointer to the left child node
    TreeNode* left; 
    // Pointer to the right child node
    TreeNode* right;

    // Constructor to initialize the node with a
    // value and set left and right pointers to null
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to check if a given binary
    // tree is a valid binary search tree (BST)
    bool isValid(TreeNode* root) {
        // Calls the helper function isValidBST
        // with initial min and max values
        return isValidBST(root, LONG_MIN, LONG_MAX); 
    }

    // Helper function to recursively validate the BST property
    bool isValidBST(TreeNode* root, long minVal, long maxVal) {
        if (root == nullptr) {
            // Base case: an empty
            // tree is a valid BST
            return true; 
        }
        
        // Checks if the current node
        // violates the BST property
        if (root->val >= maxVal || root->val <= minVal) {
            return false; 
        }

        // Recursively checks left and right
        // subtrees with updated constraints
        // that every value on its left subtree
        // should be smaller than the current node
        // and every value on its right subtree
        // should be greater than the current node
        return isValidBST(root->left, minVal, root->val)
                && isValidBST(root->right, root->val, maxVal);
    }
};




// Function to perform an in-order traversal
// of a binary tree and print its nodes
void printInOrder(TreeNode* root) {
    // Check if the current node
    // is null (base case for recursion)
    if (root == NULL) {
        // If null, return and
        // terminate the function
        return; 
    }

    // Recursively call printInOrder
    // for the left subtree
    printInOrder(root->left);
    
    // Print the value of the current node
    cout << root->val << " ";

    // Recursively call printInOrder
    // for the right subtree
    printInOrder(root->right);
}


int main() {
    Solution solution;

    // Creating a sample tree
    TreeNode* root = new TreeNode(6);
    root->left = new TreeNode(3);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    cout << "Inorder Traversal of Tree:" << endl;
    printInOrder(root);
    cout << endl;

    // Checking if the created tree is a valid BST
    bool isValidBST = solution.isValid(root);

    if (isValidBST) {
        cout << "The tree is a valid BST." << endl;
    } else {
        cout << "The tree is not a valid BST." << endl;
    }
    return 0;
}

Output:

Inorder Traversal of Tree:

2 3 4 6 7 8

The tree is a valid BST.

Time Complexity: O(N) where N is the number of nodes in the binary tree. Since we are traversing and checking each node the time complexity is proportional to the number of does in the binary tree.

Space Complexity: O(1) as no additional data structure or memory allocation is done during the traversal, though an O(N) is used as auxiliary space by the recursion stack.

Java Code

// Importing necessary packages
import java.util.*;

// Definition of TreeNode structure
// for a binary tree node
class TreeNode {
    // Value of the node
    int val;

    // Pointer to the left child node
    TreeNode left;
    // Pointer to the right child node
    TreeNode right;

    // Constructor to initialize the node with a
    // value and set left and right pointers to null
    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

class Solution {
    // Function to check if a given binary
    // tree is a valid binary search tree (BST)
    public boolean isValid(TreeNode root) {
        // Calls the helper function isValidBST
        // with initial min and max values
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // Helper function to recursively validate the BST property
    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) {
            // Base case: an empty
            // tree is a valid BST
            return true;
        }

        // Checks if the current node
        // violates the BST property
        if (root.val >= maxVal || root.val <= minVal) {
            return false;
        }

        // Recursively checks left and right
        // subtrees with updated constraints
        // that every value on its left subtree
        // should be smaller than the current node
        // and every value on its right subtree
        // should be greater than the current node
        return isValidBST(root.left, minVal, root.val)
                && isValidBST(root.right, root.val, maxVal);
    }
}

// Function to perform an in-order traversal
// of a binary tree and print its nodes
class TreeTraversal {
    public static void printInOrder(TreeNode root) {
        // Check if the current node
        // is null (base case for recursion)
        if (root == null) {
            // If null, return and
            // terminate the function
            return;
        }

        // Recursively call printInOrder
        // for the left subtree
        printInOrder(root.left);

        // Print the value of the current node
        System.out.print(root.val + " ");

        // Recursively call printInOrder
        // for the right subtree
        printInOrder(root.right);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Creating a sample tree
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(3);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        System.out.println("Inorder Traversal of Tree:");
        TreeTraversal.printInOrder(root);
        System.out.println();

        // Checking if the created tree is a valid BST
        boolean isValidBST = solution.isValid(root);

        if (isValidBST) {
            System.out.println("The tree is a valid BST.");
        } else {
            System.out.println("The tree is not a valid BST.");
        }
    }
}

Output:

Inorder Traversal of Tree:

2 3 4 6 7 8

The tree is a valid BST.

Time Complexity: O(N) where N is the number of nodes in the binary tree. Since we are traversing and checking each node the time complexity is proportional to the number of does in the binary tree.

Space Complexity: O(1) as no additional data structure or memory allocation is done during the traversal, though an O(N) is used as auxiliary space by the recursion stack.

Python Code

class TreeNode:
    """
    Definition of TreeNode structure
    for a binary tree node
    """
    def __init__(self, x):
        # Value of the node
        self.val = x
        
        # Pointer to the left child node
        self.left = None 
        # Pointer to the right child node
        self.right = None 

class Solution:
    """
    Class implementing solution
    to check if a given binary
    tree is a valid binary search tree (BST)
    """
    def isValid(self, root):
        """
        Function to check if a given binary
        tree is a valid binary search tree (BST).
        Calls the helper function isValidBST
        with initial min and max values.
        """
        return self.isValidBST(root, float('-inf'), float('inf'))

    def isValidBST(self, root, minVal, maxVal):
        """
        Helper function to recursively validate the BST property.
        """
        if not root:
            # Base case: an empty
            # tree is a valid BST
            return True
        
        # Checks if the current node
        # violates the BST property
        if root.val >= maxVal or root.val <= minVal:
            return False

        # Recursively checks left and right
        # subtrees with updated constraints
        # that every value on its left subtree
        # should be smaller than the current node
        # and every value on its right subtree
        # should be greater than the current node
        return self.isValidBST(root.left, minVal, root.val) and self.isValidBST(root.right, root.val, maxVal)


def printInOrder(root):
    """
    Function to perform an in-order traversal
    of a binary tree and print its nodes.
    """
    if not root:
        # If null, return and
        # terminate the function
        return

    # Recursively call printInOrder
    # for the left subtree
    printInOrder(root.left)
    
    # Print the value of the current node
    print(root.val, end=" ")

    # Recursively call printInOrder
    # for the right subtree
    printInOrder(root.right)


if __name__ == "__main__":
    solution = Solution()

    # Creating a sample tree
    root = TreeNode(6)
    root.left = TreeNode(3)
    root.right = TreeNode(8)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(7)
    print("Inorder Traversal of Tree:")
    printInOrder(root)
    print()

    # Checking if the created tree is a valid BST
    isValidBST = solution.isValid(root)

    if isValidBST:
        print("The tree is a valid BST.")
    else:
        print("The tree is not a valid BST.")

Output:

Inorder Traversal of Tree:

2 3 4 6 7 8

The tree is a valid BST.

Time Complexity: O(N) where N is the number of nodes in the binary tree. Since we are traversing and checking each node the time complexity is proportional to the number of does in the binary tree.

Space Complexity: O(1) as no additional data structure or memory allocation is done during the traversal, though an O(N) is used as auxiliary space by the recursion stack.

JavaScript Code

// Definition of TreeNode structure
// for a binary tree node
class TreeNode {
    // Constructor to initialize the node with a
    // value and set left and right pointers to null
    constructor(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    // Function to check if a given binary
    // tree is a valid binary search tree (BST)
    isValid(root) {
        // Calls the helper function isValidBST
        // with initial min and max values
        return this.isValidBST(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
    }

    // Helper function to recursively validate the BST property
    isValidBST(root, minVal, maxVal) {
        if (root === null) {
            // Base case: an empty
            // tree is a valid BST
            return true;
        }

        // Checks if the current node
        // violates the BST property
        if (root.val >= maxVal || root.val <= minVal) {
            return false;
        }

        // Recursively checks left and right
        // subtrees with updated constraints
        // that every value on its left subtree
        // should be smaller than the current node
        // and every value on its right subtree
        // should be greater than the current node
        return (
            this.isValidBST(root.left, minVal, root.val) &&
            this.isValidBST(root.right, root.val, maxVal)
        );
    }
}

// Function to perform an in-order traversal
// of a binary tree and print its nodes
function printInOrder(root) {
    // Check if the current node
    // is null (base case for recursion)
    if (root === null) {
        // If null, return and
        // terminate the function
        return;
    }

    // Recursively call printInOrder
    // for the left subtree
    printInOrder(root.left);

    // Print the value of the current node
    console.log(root.val + " ");

    // Recursively call printInOrder
    // for the right subtree
    printInOrder(root.right);
}

// Creating a sample tree
let root = new TreeNode(6);
root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);
console.log("Inorder Traversal of Tree:");
printInOrder(root);

// Checking if the created tree is a valid BST
let solution = new Solution();
let isValidBST = solution.isValid(root);

if (isValidBST) {
    console.log("The tree is a valid BST.");
} else {
    console.log("The tree is not a valid BST.");
}

Output:

Inorder Traversal of Tree:

2 3 4 6 7 8

The tree is a valid BST.

Time Complexity: O(N) where N is the number of nodes in the binary tree. Since we are traversing and checking each node the time complexity is proportional to the number of does in the binary tree.

Space Complexity: O(1) as no additional data structure or memory allocation is done during the traversal, though an O(N) is used as auxiliary space by the recursion stack.

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Gauri Tomar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article