Leetcode 98: Validate Binary Search Tree

An In-order traversal DFS implementation for binary search tree (BST)

Problem description

Binary search tree refresher

Tree is a node-based data structure that is intended to provide the best of the linked list and array—That is, the fast insertion and deletion characteristics of a linked list, but with the added benefit of maintaining order like an array.

Binary search tree (BST), by definition, is specifically order-maintaining — It is a special binary tree where each node has two children, and for any given node, all nodes in its left subtree are smaller than the node itself, and all the nodes in its right subtree are larger than the node itself.

In-order traversal DFS offers a natural solution for BST validation

When we write out in-order traversal sequence for a BST (reminder: in order travel always follows a left -> node -> right order), we obtain an array whose values increase from left to right as demonstrated below:

Figure 1: In-order DFS traversal example for a binary search tree; the traversal sequence is a monotonically increasing array

Intuition for recursive solution

Given the relationship between BST and in-order traversal sequence (Figure 1), we can simplify the problem the following:

1. Having a state tracker that tracks the previous node that the in-order DFS has traversed; Here we use a variable prev to track “the last node we just traversed”
2. Have a recursive implementation of in-order traversal that also compares the current node we are processing with the previous node we just visited. We denote “current node we are processing” with variable node in the left->node->right in order traversal
3. Once the comparison between prev and node is done, if BST condition prev.val < node.val is broken, we would immediately return False and stop executing further. Otherwise, we update prev with node before moving to the right node/subtree

Once this most basic process is established, the recursive implementation again becomes an exercise of “trust the process” (see also: “trust the process” elaborated in Leetcode 104: Maximum Depth of Binary Tree).

Trick: Make the `prev` tracker a non-local variable inside the recursive function

From the breakdown of the steps described above, we can also observe the non-local (local to each recursive call/call stack element itself). More specifically, we can use the following logic to set up the non-local scope of prev tracker:

prev = None
...
def recursive_function(node):
    nonlocal prev

Python solution via in-order DFS

Putting these together, we have the following implementation:

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        prev = None

        def in_order_validation(node):
            nonlocal prev

            if node is None:
                return True
            
            if not in_order_validation(node.left):
                return False
            
            if prev and prev.val >= node.val:
                return False
            
            prev = node

            return in_order_validation(node.right)
        
        return in_order_validation(root)

Space and time complexity

With n denoting the total number of nodes in the binary tree,

• Space complexity: O(h) — The DFS recursion call stack size is determined by the height of the binary tree. Best case: O(log n) for a perfectly balanced binary tree; Worst case: O(n) for completely skewed tree (essentially becomes a linked list)
• Time complexity: O(n) — Sincd in order DFS traversal iterate through each node exactly once

Example unit tests (pytest)

def test_valid_bst():
    """
          2
         / \
        1   3
    """
    root = TreeNode(2, TreeNode(1), TreeNode(3))
    assert isValidBST(root) == True


def test_invalid_bst():
    """
          5
         / \
        1   4
           / \
          3   6
    """
    root = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
    assert isValidBST(root) == False