w3resource

Python Binary Search Tree: Check a binary tree is valid or not


3. Validate BST

Write a Python program to check whether a given binary tree is a valid binary search tree (BST) or not.

Let a binary search tree (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.

Example 1:
    2
   / \
  1   3
Binary tree [2,1,3], return true.
Example 2:
    1
   / \
  2   3
Binary tree [1,2,3], return false.

Sample Solution:

Python Code:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def is_BST(root):
    stack = []
    prev = None
    
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if prev and root.val <= prev.val:
            return False
        prev = root
        root = root.right
    return True

root = TreeNode(2)  
root.left = TreeNode(1)  
root.right = TreeNode(3) 
 
result = is_BST(root)
print(result)

root = TreeNode(1)  
root.left = TreeNode(2)  
root.right = TreeNode(3) 
 
result = is_BST(root)
print(result)

Sample Output:

True
False

Flowchart:

Flowchart: Check a binary tree is valid or not.

For more Practice: Solve these Related Problems:

  • Write a Python program to check if a binary tree is a valid BST using in-order traversal and compare the resulting list with its sorted version.
  • Write a Python script to recursively validate a BST by ensuring each node’s value lies within a valid range, then test it on a tree with duplicate values.
  • Write a Python program to implement an iterative BST validation algorithm using a stack and then output whether the tree is valid.
  • Write a Python function to determine if a binary tree is a valid BST and also print the minimum and maximum values found in each subtree.

Go to:


Previous: Write a Python program to find the closest value of a given target value in a given non-empty Binary Search Tree (BST) of unique values.
Next: Write a Python program to delete a node with the given key in a given Binary search tree (BST).

Python Code Editor:

Contribute your code and comments through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.