Validate Binary Search Tree

To check if a binary tree is a valid Binary Search Tree (BST), you can perform an in-order traversal and check that the nodes are visited in strictly ascending order. This will ensure that the left subtree has values less than the root’s value, and the right subtree has values greater than the root’s value, as well as ensuring the subtrees themselves are BSTs.

Here’s a code snippet to determine if a given binary tree is a valid BST:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def inOrderTraversal(node, prev):
            if not node:
                return True

            # Traverse the left subtree
            if not inOrderTraversal(node.left, prev):
                return False

            # Check if the current node's value is greater than the previous node's value
            if prev[0] is not None and node.val <= prev[0].val:
                return False

            # Update the previous node to the current node
            prev[0] = node
            
            # Traverse the right subtree
            return inOrderTraversal(node.right, prev)

        return inOrderTraversal(root, [None])

This code uses a recursive in-order traversal, where prev is a one-element list that keeps track of the previously visited node. If at any point a node is encountered that does not have a value greater than the previous node’s value, the function returns False. If the traversal completes without finding any violations of the BST property, the function returns True.

The time complexity of this function is (O(n)), where (n) is the number of nodes in the tree, and the space complexity is (O(h)), where (h) is the height of the tree.

title: Valid Binary Search Tree tags: data-flow-direction top-down-tree-processing

The key to solving this problem is to pass the range for each recursive call to make sure that binary search tree property holds for all nodes, not just the parent and child nodes, BST must be valid for nodes that are even further apart. The data flows from the parent to children.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def valid?(node, lower = -Float::INFINITY, upper = Float::INFINITY)
  # The leaf node does not have any child so comparison cannot be made
  if node.nil? 
    return true
  end
  
  # Unit of work  
  val = node.val
  
  # BST property check  
  if val <= lower or val >= upper
    return false
  end
  
  # early termination condition for right child
  unless valid?(node.right, val, upper)
    return false 
  end
  
  # early termination condition for left child
  unless valid?(node.left, lower, val)
    return false
  end

  return true
end

# @param {TreeNode} root
# @return {Boolean}
def is_valid_bst(root)
  valid?(root)
end
  1. Recursive: left subtree, right subtree. Recursive cases.
  2. Base cases: 1
  3. What is the unit of work ? Check to see root.left.val node < root > root.right.val node
  4. How do we handle both left and right subtrees are also binary search trees
  5. We have to have a range to check if the nodes satisfy the invariant
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Boolean}

def valid?(node, lower = -Float::INFINITY, upper = Float::INFINITY)  
    if node.nil? 
        return true
    end

    val = node.val

    if val <= lower or val >= upper
        return false
    end

    unless valid?(node.right, val, upper)
       return false 
    end

    unless valid?(node.left, lower, val)
        return false
    end

    return true 
end

def is_valid_bst(root)
    valid?(root)
end

Identifying Problem Isomorphism

“Validate Binary Search Tree” asks you to check if a given tree is a valid Binary Search Tree (BST), which requires checking if the left child of a node is less than the node and the right child is greater than the node, for all nodes.

An isomorphic problem to this is “Recover Binary Search Tree” (LeetCode #99). In this problem, you are given a binary search tree where two nodes have been swapped by mistake, and you have to recover the tree without changing its structure.

To solve both problems, you can use an inorder traversal. In “Validate Binary Search Tree”, you check if each node is greater than the previous one in the inorder traversal. In “Recover Binary Search Tree”, you also do an inorder traversal and look for nodes that are smaller than the previous node, indicating that they are out of place. Then you swap the nodes to fix the BST.

These problems have isomorphism in the sense that they both involve understanding properties of BSTs and using an inorder traversal. They are not exactly identical problems as one involves validating a BST while the other involves fixing a BST.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = float('-inf')
        def inorder(node):
            nonlocal prev
            if not node:
                return True
            if not (inorder(node.left) and prev < node.val):
                return False
            prev = node.val
            return inorder(node.right)
        return inorder(root)

Problem Classification

Language Agnostic Coding Drills

  1. Understanding Trees: Understanding the basic concept of tree data structure and its terminology like root, child, sibling, leaf, etc.

  2. Creating a Class: Create a class with its attributes and methods.

  3. Recursive Functions: Understand the concept of recursion and how to use recursive functions to solve problems.

  4. Binary Search Trees: Learn about Binary Search Trees (BST) and their properties. Write a function to check whether a given binary tree is a BST or not.

  5. Inorder Tree Traversal: Understand the inorder tree traversal algorithm and write a function to perform inorder traversal of a binary tree.

  6. Optional and Nonlocal Keywords: Understand the use of optional and nonlocal keywords in Python. Optional keyword is used to specify that the parameter of a function or method is optional. Nonlocal keyword is used to specify that a variable is not local to the function or method in which it is declared.

Targeted Drills in Python

  1. Understanding Trees: Create a simple tree data structure and practice accessing its nodes and values.

  2. Creating a Class:

1
2
3

class MyClass:
    def __init__(self, val):
        self.val = val
  1. Recursive Functions:
1
2
3
4
5

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

  1. Binary Search Trees: Write a function to check whether a given binary tree is a BST or not.

  2. Inorder Tree Traversal:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val),
        inorder(root.right)
  1. Optional and Nonlocal Keywords:
1
2
3
4
5
6
7
8

def outer_function():
    a = 5
    def inner_function():
        nonlocal a
        a = 10
    inner_function()
    print(a)
outer_function()  # Output: 10