DSA Visualizations | Hello Interview

Validate Binary Search Tree

DESCRIPTION (credit Leetcode.com)

Given the root of a binary, write a recursive function to determine if it is a valid binary search tree.

EXAMPLES

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A tree is a BST if the following conditions are met:

Every node on the left subtree has a value less than the value of the current node.
Every node on the right subtree has a value greater than the value of the current node.
The left and right subtrees must also be valid BSTs.

Example 1:

Input:


[2,1,4]

Output: true

Example 2:

Input:


[4,1,5,null,null,3,6]

Output: false. 3 is the the root node's right subtree, but it is less than the root node 4.

Run your code to see results here

Explanation

Let's think about what it means for a binary tree to be a valid binary search tree. For a binary tree to be a valid binary search tree, the following conditions must be true:

Every node in the left subtree of the root node must have a value less than the value of the root node.
Every node in the right subtree of the root node must have a value greater than the value of the root node.

This definition is true for every subtree in the node.

We can use that definition to validate a binary search tree by having parents pass values down to their children. Let's say we are validating this binary search tree:

Based on the definition of a valid binary search tree, any value in the left subtree must be less than 4, but there is no limit to how small the values are.

So we can pass max = 4 and min = -inf to the left child as a range of valid values of the left subtree.

From there, for the subtree rooted at node 2:

The max value of any node in the left subtree 2 is 2, and the min value is still -inf.

Any value in the right subtree must be greater than the 2, but also less than 4 (the value of the root node). So we can pass max = 4 and min = 2 to the right child as a range of valid values of the right subtree.

We can visit each node in the tree, and have the parent pass down the range of valid values to their children in this fashion. If the current node's value falls outside of the valid range, we can return False immediately. If we reach the empty subtree, this means that we have not yet found an invalid node yet, and we can return True.

Return Values

If I'm at a node in the tree, what values do I need from my left and right children to tell if the current subtree is a valid binary search tree?

The current subtree is a valid binary search tree if:

The left subtree is a valid binary search tree.
The right subtree is a valid binary search tree.
And the value of the current node falls within the valid range.

This tells me that each recursive call should return a boolean value indicating whether the current subtree is a valid binary search tree.

Base Case

An empty tree is a valid binary search tree.

Extra Work The work that we need to do at each node is to check if the current node's value falls within the valid range. If it doesn't we can return False immediately.

Helper Functions

Since we need to pass the minimum and maximum values down to their children, we need to introduce a helper function to keep track of these values.

This helper function will introduce two parameters, min_ and max_, which represent the range of values that the current subtree's nodes can take on. The helper function will return a boolean value indicating whether the current subtree is a valid binary search tree.

When we recurse to our left child, we:

Pass the current node's value as the new max_ value, since the left child's value must be less than the current node's value. min_ remains the same.

When we recurse to our right child, we:

Pass the current node's value as the new min_ value, since the right child's value must be greater than the current node's value. max_ remains the same.

Global Variables The return value of the helper function matches the answer to the problem, so we don't need to use any global variables.

Solution

class Solution:
    def validateBST(self, root):
        def dfs(node, min_, max_):
            # base case
            if node is None:
                return True

            # check if the current node's value is within the valid range
            if node.val <= min_ or node.val >= max_:
                return False

            return dfs(node.left, min_, node.val) and dfs(node.right, node.val, max_)

        return dfs(root, float('-inf'), float('inf'))

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node via each recursive call to dfs exactly once. Each recursive call does a constant amount of work.

Space Complexity: O(N), where N is the number of nodes in the binary tree, for the space that it takes to allocate each recursive call frame on the call stack.

Next: Calculate Tilt

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Helper Functions and Global Variables

Calculate Tilt

Validate Binary Search Tree

DESCRIPTION (credit Leetcode.com)

Given the root of a binary, write a recursive function to determine if it is a valid binary search tree.

EXAMPLES

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A tree is a BST if the following conditions are met:

Every node on the left subtree has a value less than the value of the current node.
Every node on the right subtree has a value greater than the value of the current node.
The left and right subtrees must also be valid BSTs.

Example 1:

Input:


[2,1,4]

Output: true

Example 2:

Input:


[4,1,5,null,null,3,6]

Output: false. 3 is the the root node's right subtree, but it is less than the root node 4.

Run your code to see results here

Explanation

Let's think about what it means for a binary tree to be a valid binary search tree. For a binary tree to be a valid binary search tree, the following conditions must be true:

Every node in the left subtree of the root node must have a value less than the value of the root node.
Every node in the right subtree of the root node must have a value greater than the value of the root node.

This definition is true for every subtree in the node.

We can use that definition to validate a binary search tree by having parents pass values down to their children. Let's say we are validating this binary search tree:

Based on the definition of a valid binary search tree, any value in the left subtree must be less than 4, but there is no limit to how small the values are.

So we can pass max = 4 and min = -inf to the left child as a range of valid values of the left subtree.

From there, for the subtree rooted at node 2:

The max value of any node in the left subtree 2 is 2, and the min value is still -inf.

Return Values

If I'm at a node in the tree, what values do I need from my left and right children to tell if the current subtree is a valid binary search tree?

The current subtree is a valid binary search tree if:

The left subtree is a valid binary search tree.
The right subtree is a valid binary search tree.
And the value of the current node falls within the valid range.

This tells me that each recursive call should return a boolean value indicating whether the current subtree is a valid binary search tree.

Base Case

An empty tree is a valid binary search tree.

Extra Work The work that we need to do at each node is to check if the current node's value falls within the valid range. If it doesn't we can return False immediately.

Helper Functions

Since we need to pass the minimum and maximum values down to their children, we need to introduce a helper function to keep track of these values.

When we recurse to our left child, we:

Pass the current node's value as the new max_ value, since the left child's value must be less than the current node's value. min_ remains the same.

When we recurse to our right child, we:

Pass the current node's value as the new min_ value, since the right child's value must be greater than the current node's value. max_ remains the same.

Global Variables The return value of the helper function matches the answer to the problem, so we don't need to use any global variables.

Solution

class Solution:
    def validateBST(self, root):
        def dfs(node, min_, max_):
            # base case
            if node is None:
                return True

            # check if the current node's value is within the valid range
            if node.val <= min_ or node.val >= max_:
                return False

            return dfs(node.left, min_, node.val) and dfs(node.right, node.val, max_)

        return dfs(root, float('-inf'), float('inf'))

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node via each recursive call to dfs exactly once. Each recursive call does a constant amount of work.

Space Complexity: O(N), where N is the number of nodes in the binary tree, for the space that it takes to allocate each recursive call frame on the call stack.

Next: Calculate Tilt

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103