🔟98. Validate Binary Search Tree

medium | grind 75 | Wednesday 13, 2022

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.

Example 2

invalid binary tree

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Example 1

valid binary tree

Input: root = [2,1,3]
Output: true

I have to be honest, When I saw this question first, I forgot my preorder, inorder and postorder traversal so I was complicating it a lot more than it had to. However, after a few tries, I realized this is can be easily solved using an inorder traversal method. Inorder traversal: visit left most node, then the current node, and then the right node. Inorder traversal retrieves all the values in ascending order. Therefore, if we find that the inorder traversal returns values not in ascending order, then we know the binary tree is invalid.

Example 2

In example 2, we start with the root node 5. Given that we have a left node we visit node 1. We then visit the left of node 1. However, since it is empty it returns. Once the recursion returns, we append the current node's value which is node 1 since line 19 is right after line 18(left recursion). Now we go to the right of node 1, and since it is empty we return. NOTE: We do not append node 1 because the append happens only after traversing the left side.

We first started our recursion with node 5, since we are finished with node 1, which was the left node recursion, we append the root node 5. Now the right side of node 5 gets triggered. Once this happens, this is go to the leftmost nodes and the same process as node 1 will follow.

Once we have traversed through all the nodes, we iterate over our nodes list. If the binary tree is valid, the values in the nodes should be sorted in ascending order. If we find any value that is bigger than the next value in nodes, then we return false, because the values are not sorted.

I have seen better solutions to this, especially in terms of space used. I use O(n) where n is the number of nodes space whereas there are other solutions with O(1) space complexity.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        nodes = []  # to store the sorted ascending values
        self.dfs(root, nodes) 
        
        # if the values are not in ascending order, we know it is invalid
        for i in range(len(nodes)): 
            if i+1 <= len(nodes)-1: 
                if nodes[i] >= nodes[i+1]: 
                    return False
        return True
        
    def dfs(self, root, nodes): 
        if root == None: # when you get to the end/after leaf node, you return 
            return
        
        self.dfs(root.left, nodes) # traverse all the way to the end of left node
        nodes.append(root.val) # append the current node
        self.dfs(root.right, nodes) # visit the right node

TIME AND SPACE COMPLEXITY:

TIME: O(n) where n is the number of nodes. We visit every single nodes once.

SPACE: O(n) when n is the number of nodes. Given that we are storing the n values in the list.