What is the time complexity of Validate Binary Search Tree?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Validate Binary Search Tree?

This problem uses Tree, Depth-First Search, Binary Search Tree, Binary Tree. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Validate Binary Search Tree?

Insight 1: The core idea is to perform a recursive traversal of the tree while maintaining a valid range (lower bound and upper bound) for each node's value. Initially, the range is unbounded (negative infinity to positive infinity). Insight 2: For a node to be valid, its value must fall within the current range. If it does, we recursively check its left subtree with the upper bound updated to the node's value, and its right subtree with the lower bound updated to the node's value.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Validate Binary Search Tree - LeetCode 98 Solution

Q: Which companies ask LeetCode 98. Validate Binary Search Tree in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Arista Networks, Bloomberg and 16 more companies.

Validate Binary Search Tree - Complete Solution Guide

Validate Binary Search Tree is LeetCode problem 98, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 strictly less than the node's key. The right subtree of a node contains only nodes with keys strictly 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

Detailed Explanation

The problem asks us to determine whether a given binary tree is a valid Binary Search Tree (BST). A valid BST has the following properties: 1. For each node, all nodes in its left subtree must have values strictly less than the node's value. 2. For each node, all nodes in its right subtree must have values strictly greater than the node's value. 3. Both the left and right subtrees of a node must also be valid BSTs. The input is the root of the binary tree. The output is a boolean value indicating whether the tree is a valid BST.

Solution Approach

The provided solution employs a recursive Depth-First Search (DFS) approach to traverse the binary tree. The `validate` function takes a node, a lower bound (`low`), and an upper bound (`high`) as input. It recursively checks if the node's value falls within the specified range. If it doesn't, the tree is not a valid BST. If the node is valid, the function then recursively checks the left subtree, updating the upper bound to the node's value, and the right subtree, updating the lower bound to the node's value. The base case for the recursion is when the node is null, in which case we return `true` (an empty tree is a valid BST).

Step-by-Step Algorithm

Step 1: Initialize the `validate` function with the root node, a lower bound of negative infinity, and an upper bound of positive infinity.
Step 2: In the `validate` function, check if the current node is null. If it is, return `true`.
Step 3: Check if the current node's value is within the specified range (strictly greater than the lower bound and strictly less than the upper bound). If it is not, return `false`.
Step 4: Recursively call the `validate` function for the left subtree, passing the current node's `low` value as the lower bound and the current node's value as the upper bound.
Step 5: Recursively call the `validate` function for the right subtree, passing the current node's value as the lower bound and the current node's `high` value as the upper bound.
Step 6: Return `true` if both the left and right subtrees are valid BSTs according to the recursive calls; otherwise return `false`.

Key Insights

Insight 1: The core idea is to perform a recursive traversal of the tree while maintaining a valid range (lower bound and upper bound) for each node's value. Initially, the range is unbounded (negative infinity to positive infinity).
Insight 2: For a node to be valid, its value must fall within the current range. If it does, we recursively check its left subtree with the upper bound updated to the node's value, and its right subtree with the lower bound updated to the node's value.
Insight 3: Using long or double instead of int for low and high values is crucial to handle the edge cases where node values can be equal to the minimum or maximum integer values.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Tree, Depth-First Search, Binary Search Tree, Binary Tree.

Companies

Asked at: Adobe, Amazon, Apple, Arista Networks, Bloomberg, Citadel, IBM, LinkedIn, Meta, Microsoft, Nvidia, Oracle, SIG, Salesforce, ServiceNow, TikTok, Uber, Wix, Yahoo, Yandex, eBay.

Validate Binary Search Tree | LeetCode 98

Medium

Tree Depth-First Search Binary Search Tree Binary Tree

Time: O(n)Space: O(n)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
    }

    private boolean validate(TreeNode node, double low, double high) {
        if (node == null) {
            return true;
        }

        if (!(low < node.val && node.val < high)) {
            return false;
        }

        return (validate(node.left, low, node.val) &&
                validate(node.right, node.val, high));
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 98: Validate Binary Search Tree - Detailed explanation and solution approaches.

Topics

Tree Depth-First Search Binary Search Tree Binary Tree

Companies

AdobeAmazonAppleArista NetworksBloombergCitadelIBMLinkedIn

Stats

Difficulty:Medium

Languages:4

Companies:21

Problem #:98

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize the `validate` function with the root node, a lower bound of negative infinity, and an upper bound of positive infinity.
2
Step 2: In the `validate` function, check if the current node is null. If it is, return `true`.
3
Step 3: Check if the current node's value is within the specified range (strictly greater than the lower bound and strictly less than the upper bound). If it is not, return `false`.
4
Step 4: Recursively call the `validate` function for the left subtree, passing the current node's `low` value as the lower bound and the current node's value as the upper bound.
5
Step 5: Recursively call the `validate` function for the right subtree, passing the current node's value as the lower bound and the current node's `high` value as the upper bound.
6
Step 6: Return `true` if both the left and right subtrees are valid BSTs according to the recursive calls; otherwise return `false`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n) because we visit each node once. The space complexity is O(n) in the worst case due to the recursion stack. In a balanced tree, the space complexity would be O(log n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Inorder Traversal

Perform an inorder traversal of the tree and store the visited node values in an array. Then, check if the array is sorted in ascending order. If it is, the tree is a valid BST.

Time: O(n)Space: O(n)

Trade-offs: This approach requires extra space to store the inorder traversal, whereas the recursive approach uses stack space implicitly. The inorder traversal approach might be slightly easier to understand for some, but it also introduces the overhead of maintaining an array.

✨

Key Insights

1Insight 1: The core idea is to perform a recursive traversal of the tree while maintaining a valid range (lower bound and upper bound) for each node's value. Initially, the range is unbounded (negative infinity to positive infinity).
2Insight 2: For a node to be valid, its value must fall within the current range. If it does, we recursively check its left subtree with the upper bound updated to the node's value, and its right subtree with the lower bound updated to the node's value.
3Insight 3: Using long or double instead of int for low and high values is crucial to handle the edge cases where node values can be equal to the minimum or maximum integer values.

📚

Key Terms Explained

For Students

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty tree (root is null). The algorithm correctly handles this case by returning `true` immediately in the base case of the `validate` function.
Edge case 2: Nodes with values equal to the minimum or maximum integer values. If low and high were int, these cases would fail if node.val was exactly INT_MIN or INT_MAX. Using long or double avoids this. This is critical because a BST requires *strict* inequality.
Edge case 3: Duplicate values within the tree. If a left subtree contains a value equal to its parent's value, the tree is not a valid BST. The strict inequality check `low < node.val < high` ensures this condition is handled correctly. If the code had `<=` instead of `<`, it would incorrectly validate BSTs with duplicates.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly using non-strict inequality (<=) instead of strict inequality (<) when comparing node values with the lower and upper bounds. This will lead to incorrect validation of trees with duplicate values.

✗Common mistake 2: Not considering the entire range of values in the subtrees. For example, only checking if the left child's value is less than the parent's value, but not ensuring that all values in the left subtree are less than the parent's value. This requires passing down the valid range from the root.

✗Common mistake 3: Failing to handle integer overflow when comparing node values that are close to INT_MIN or INT_MAX. This can be resolved by using larger data types like `long` or `double` to represent the lower and upper bounds.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Database indexing. BSTs are used to create indexes for database tables, allowing for efficient searching and retrieval of data.

🏦Real-world scenario 2: Symbol tables in compilers. Compilers use symbol tables to store information about variables, functions, and other program elements. BSTs can be used to implement symbol tables, providing fast lookups and insertions.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Most tree problems can be solved recursively. The base case is usually a null node. Think about what information needs to flow up vs down the tree.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Not handling null nodes properly. Always check if the current node exists before accessing its children.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 7, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

❓

Frequently Asked Questions

How do I choose between recursive and iterative tree traversal?

Use recursive traversal for cleaner code when stack depth isn't a concern (tree height < ~1000). Use iterative with explicit stack for very deep trees to avoid stack overflow. Iterative is also preferred when you need fine-grained control over the traversal process.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Validate Binary Search Tree"?

For this medium-level Tree problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?