98. Validate Binary Search Tree

MediumTreeDepth-First SearchBinary Search TreeBinary Tree
Leetcode Link

Problem Description

The problem asks to verify whether a given binary tree is a valid binary search tree (BST). By definition, a valid BST is characterized by the following properties:

  • Every node's left subtree contains only nodes with keys that are less than the node's own key.
  • Every node's right subtree contains only nodes with keys that are greater than the node's own key.
  • Both the left and right subtrees must also themselves be valid BSTs.

The objective is to use these criteria to check every node in the tree and ensure that the structure adheres to the rules of a BST.

Intuition

The solution uses the concept of in-order traversal. In a BST, an in-order traversal yields the nodes' values in ascending order. The approach involves a Depth-First Search (DFS) where we traverse the tree in an in-order manner (left, node, right), keeping track of the value of the previously visited node (prev). During the traversal, we ensure that each subsequent node has a greater value than the previous node.

  1. A recursive function dfs is defined, which will do an in-order traversal of the tree.
  2. If we encounter a None (indicative of reaching the end of a path), we return True, because an empty tree is technically a valid BST.
  3. As we traverse the left subtree, we check for violations of the BST properties.
  4. Before visiting the current node, we ensure that we've finished validating the left subtree. If the left subtree is invalid, the function returns False.
  5. We then check the current node's value against prev (the previous node's value, initialized to negative infinity). The value must be strictly greater to satisfy BST conditions.
  6. Update prev to the current node's value.
  7. Proceed to validate the right subtree.
  8. If every recursive call returns True, the entire tree is a valid BST, and thus the function returns True.

This approach ensures that we confirm the BST property where each node's value must be greater than all values in its left subtree and less than all values in its right subtree.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The provided Python code implements the DFS in-order traversal to check the validity of the BST, and it uses the TreeNode data structure, which is a standard representation of a node in a binary tree, consisting of a value val and pointers to left and right child nodes.

Here is the step-by-step breakdown of the solution approach:

  1. In-order traversal (DFS): We recursively traverse the binary tree using in-order traversal, where we first visit the left subtree, then the node, and finally the right subtree.

  2. Global variable: A global variable prev (initialized to negative infinity) is used to keep track of the value of the last visited node in the traversal.

  3. Checking BST properties:

    • When visiting a node, we first call the dfs function on its left child. If this function call returns False, it means the left subtree contains a violation of the BST rules, and thus, we return False immediately to stop checking further.
    • After checking the left subtree, we examine the current node by comparing its value with prev. If the current node's value is less than or equal to prev, this means the in-order traversal sequence is broken, and hence, the tree is not a valid BST. We return False in this case.
    • The prev variable is then updated to the current node's value, indicating that this node has been processed, and we move to the right subtree.

  4. Recursive base case: For a None node, which signifies the end of a branch, the dfs function returns True, as an empty tree or subtree is valid by definition.

  5. Final validation: After the entire tree has been traversed, if no violations were found, the initial call to dfs(root) will ultimately return True, confirming the tree is a valid BST.

The key algorithmic pattern used here is recursion, combined with the properties of in-order traversal for a BST. The recursive function dfs combines the logic for traversal and validation, effectively checking the BST properties as it moves through the tree.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example Walkthrough

Let's consider a small binary tree with the following structure to illustrate the solution approach:

1    2
2   / \
3  1   3

Our target is to walk through the solution approach provided above and confirm whether this tree is a valid BST.

  1. Step 1 - In-order traversal (DFS): We begin the depth-first search (DFS) with an in-order traversal from the root node which is 2. The in-order traversal dictates that we visit the left subtree first, then the root node, and finally the right subtree.

  2. Step 2 - Global variable: Initially, the prev variable is set to negative infinity. It will help us to keep track of the last visited node's value.

  3. Step 3 - Checking BST properties:

    • We start with the left child (node 1). Since node 1 has no children, we compare it to prev, which is negative infinity. Node 1 is greater, so we update prev to 1, and then we return back to node 2.
    • Now, we are at node 2 and compare its value with prev which is now 1. The value of node 2 is greater; therefore, it satisfies the BST condition. We update prev to 2 and proceed to the right subtree.
    • In the right subtree, we have node 3. We call the dfs function on node 3. As it has no children, we compare it to prev (which is now 2). Node 3 is greater than 2, so we update prev to 3.

  4. Step 4 - Recursive base case: Since we reached the leaf nodes without encountering any None nodes, we confirm that all subtrees are valid BSTs as well.

  5. Step 5 - Final validation: After visiting all the nodes following the in-order traversal, and none of the recursive dfs calls returned False, the whole tree is thus confirmed to be a valid BST. The final call to dfs(root) returns True.

By following the in-order traversal method and checking each node against the previous node's value, we have verified that the given tree meets all the properties of a valid BST:

  • Each node's left subtree contains only nodes with values less than the node's own value.
  • Each node's right subtree contains only nodes with values greater than the node's own value.
  • All the subtrees are valid BSTs on their own.

In summary, the example binary tree with nodes 1, 2, and 3 is indeed a valid binary search tree.

Solution Implementation

1class TreeNode:
2    # A binary tree node has a value, and references to left and right child nodes.
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def isValidBST(self, root: TreeNode) -> bool:
10        # Helper function to perform an in-order traversal of the tree.
11        def in_order_traversal(node):
12            nonlocal last_value_visited  # To keep track of the last value visited in in-order traversal.
13          
14            # If the current node is None, it's a leaf, so return True.
15            if node is None:
16                return True
17          
18            # Traverse the left subtree.
19            if not in_order_traversal(node.left):
20                return False
21          
22            # Check if the previous value in the in-order traversal is greater than or equal to the current node value,
23            # which would violate the BST property.
24            if last_value_visited >= node.val:
25                return False
26          
27            # Update the last value visited with the current node's value.
28            last_value_visited = node.val
29          
30            # Traverse the right subtree.
31            if not in_order_traversal(node.right):
32                return False
33          
34            # No violations found, return True.
35            return True
36
37        # We initialize the last visited value with negative infinity (smallest possible value)
38        # to make sure the first comparison is always True.
39        last_value_visited = float('-inf')
40      
41        # Start the in-order traversal of the tree with the root node.
42        return in_order_traversal(root)
43
1/**
2 * Definition for a binary tree node.
3 * This class represents a node of a binary tree which includes value, pointer to left child
4 * and pointer to right child.
5 */
6class TreeNode {
7    int val; // node's value
8    TreeNode left; // pointer to left child
9    TreeNode right; // pointer to right child
10
11    // Default constructor.
12    TreeNode() {}
13
14    // Constructor with node value.
15    TreeNode(int val) {
16        this.val = val;
17    }
18
19    // Constructor with node value, left child, and right child.
20    TreeNode(int val, TreeNode left, TreeNode right) {
21        this.val = val;
22        this.left = left;
23        this.right = right;
24    }
25}
26
27/**
28 * This class contains method to validate if a binary tree is a binary search tree (BST).
29 */
30class Solution {
31    private Integer previousValue; // variable to store the previously visited node's value
32
33    /**
34     * Validates if the given binary tree is a valid binary search tree (BST).
35     *
36     * @param root The root of the binary tree to check.
37     * @return true if the given tree is a BST, false otherwise.
38     */
39    public boolean isValidBST(TreeNode root) {
40        previousValue = null; // Initialize previousValue as null before starting traversal
41        return inOrderTraversal(root);
42    }
43
44    /**
45     * Performs an in-order depth-first traversal on the binary tree to validate BST property.
46     * It ensures that every node's value is greater than the values of all nodes in its left subtree
47     * and less than the values of all nodes in its right subtree.
48     *
49     * @param node The current node being visited in the traversal.
50     * @return true if the subtree rooted at 'node' satisfies BST properties, false otherwise.
51     */
52    private boolean inOrderTraversal(TreeNode node) {
53        if (node == null) {
54            return true; // Base case: An empty tree is a valid BST.
55        }
56        // Traverse the left subtree. If it's not a valid BST, return false immediately.
57        if (!inOrderTraversal(node.left)) {
58            return false;
59        }
60        // Check the current node value with the previous node's value.
61        // As it's an in-order traversal, previousValue should be less than the current node's value.
62        if (previousValue != null && previousValue >= node.val) {
63            return false; // The BST property is violated.
64        }
65        previousValue = node.val; // Update previousValue with the current node's value.
66        // Traverse the right subtree. If it's not a valid BST, return false immediately.
67        if (!inOrderTraversal(node.right)) {
68            return false;
69        }
70        return true; // All checks passed, it's a valid BST.
71    }
72}
73
1#include <climits>
2
3/**
4 * Definition for a binary tree node.
5 */
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    // Constructor to initialize a node with a given value,
11    // with left and right pointers set to nullptr by default
12    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13    // Constructor to create a node with given value, left, and right children
14    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
15};
16
17class Solution {
18private:
19    // Pointer to store the last visited node in the binary search tree
20    // to compare its value with the current node's value.
21    TreeNode* lastVisited;
22
23    // Helper function to perform an in-order traversal of the tree
24    // and check if it is a valid binary search tree.
25    bool inorderTraversal(TreeNode* node) {
26        // Base case: If the current node is null, then it's valid
27        if (!node) return true;
28
29        // Recursively traverse the left subtree.
30        // If the left subtree is not a valid BST, the entire tree is not.
31        if (!inorderTraversal(node->left)) return false;
32
33        // If the last visited node is not null and the value of the last visited node
34        // is greater than or equal to the current node's value, then it's not a valid BST.
35        if (lastVisited && lastVisited->val >= node->val) return false;
36
37        // Update the last visited node to the current node
38        lastVisited = node;
39
40        // Recursively traverse the right subtree.
41        // If the right subtree is not a valid BST, the entire tree is not.
42        if (!inorderTraversal(node->right)) return false;
43
44        // If both subtrees are valid, return true
45        return true;
46    }
47
48public:
49    // Function to check whether a binary tree is a valid binary search tree.
50    bool isValidBST(TreeNode* root) {
51        // Initialize the last visited node as null before starting the traversal
52        lastVisited = nullptr;
53
54        // Call the helper function to check if the tree is a valid BST
55        return inorderTraversal(root);
56    }
57};
58
1// Define the structure of a TreeNode with TypeScript interface
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8/**
9 * Validates if the provided tree is a binary search tree.
10 * @param {TreeNode | null} root - The root node of the binary tree to validate.
11 * @return {boolean} - True if the tree is a valid BST; otherwise, false.
12 */
13const isValidBST = (root: TreeNode | null): boolean => {
14  // Define the previous node to keep track of during in-order traversal
15  let previous: TreeNode | null = null;
16
17  /**
18   * Performs in-order traversal to check each node's value strictly increasing.
19   * @param {TreeNode | null} node - The current node in the traversal.
20   * @return {boolean} - True if the subtree is valid; otherwise, false.
21   */
22  const inorderTraversal = (node: TreeNode | null): boolean => {
23    if (node === null) {
24      return true;
25    }
26
27    // Traverse the left subtree
28    if (!inorderTraversal(node.left)) {
29      return false;
30    }
31
32    // Check if the current node's value is greater than the previous node's value
33    if (previous && node.val <= previous.val) {
34      return false;
35    }
36
37    // Update the previous node to the current node
38    previous = node;
39
40    // Traverse the right subtree
41    return inorderTraversal(node.right);
42  };
43
44  // Start the recursive in-order traversal from the root
45  return inorderTraversal(root);
46};
47
48// Sample usage (in TypeScript you would normally type the input, here it is implicit for brevity)
49// let tree: TreeNode = {
50//   val: 2,
51//   left: { val: 1, left: null, right: null },
52//   right: { val: 3, left: null, right: null }
53// };
54// console.log(isValidBST(tree)); // Outputs: true
55
Not Sure What to Study? Take the 2-min Quiz๏ผš

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Time and Space Complexity

The given Python code defines a method isValidBST to determine if a binary tree is a valid binary search tree. It uses depth-first search (DFS) to traverse the tree.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because the DFS visits each node exactly once to compare its value with the previously visited node's value.

Space Complexity:

The space complexity of this code is O(h), where h is the height of the tree. This is determined by the maximum number of function calls on the call stack at any one time, which occurs when the algorithm is traversing down one side of the tree. In the worst case of a completely unbalanced tree (like a linked list), the space complexity would be O(n). For a balanced tree, it would be O(log n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Search Tree Intro

Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ