98. Validate Binary Search Tree

Description of the Problem

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 1:

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

Example 2:

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.

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1

Solution

Tags: Binary Search Tree

Explanation

The problem itself explains how to form a solution.

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.

To check the above properies, each parent node must know the in-order traversal of both sub-trees. When in-order traversals are available, they can be compared with the parent value.

To speed up the evaluation of the properties, the recursive function return true when the properties are matched, otherwise it return false. If parent node receives false from a child, the function skips the comparsion (Reminder: The order of boolean expressions matters).

Code

use std::rc::Rc;
use std::cell::RefCell;
impl Solution{
    pub fn is_valid_bst(root : Option<Rc<RefCell<TreeNode>>>) -> bool {
        let (is_valid, _) = Solution::verify(root);
        return is_valid;
    }

    fn verify(node : Option<Rc<RefCell<TreeNode>>>) -> (bool, Vec<i32>){
        if let Some(node) = node {
            let node = node.borrow();
            let (is_left_valid, mut left_vec) = Solution::verify(node.left.clone());
            let (is_right_valid, right_vec) = Solution::verify(node.right.clone());
            let is_this_valid = is_left_valid && is_right_valid 
                && left_vec.iter().all( |l| *l < node.val )
                && right_vec.iter().all( |r| node.val < *r );
            left_vec.push(node.val);
            left_vec.extend(right_vec);
            return (is_this_valid, left_vec);
        }

        return (true, vec![]);
    }
}

Complexity

n is the number of node and h is height of tree

Time complexity:

Worst case: \(O(n^2)\)
- Recursive formula: \( T(n) = T(n-1) + T(1) + cn \)
For balance tree: \(O(n \log n)\)
- Recursive formula: \( T(n) = 2 \ T(n/2) + cn \)

Auxiliary Space:

\( O(n) \)
- The size of call stack and list of number are bound by height of the tree and the number of nodes. Also, the height cannot exceed the number of tree nodes.

Leetbook