Recursion
Validate BST
Given the root of a tree root, return whether the tree is a BST or not. The values in the tree are all unique.
Example 1:
Example 2:
Explanation 2: The tree is not a BST because when you move left, you get a larger value. You should instead get a smaller value.
There are 2 ways you can solve this problem.
Using an inorder traversal:
0. Problem
To solve this problem, you can realize that inorder traversals visit values in a BST from smallest to largest (like in the last problem). If the inorder traversal visits nodes in increasing order, then the tree is a BST. Otherwise it's not a BST.
1. Recursion
The recursion for an inorder traversal is this:
2. Base case
The inorder traversal should stop when it gets to a node that's null. It should also stop if we know the tree is not a BST since there's no point in continuing.
3. Code
To code the solution, we just combine the recursion and base case.
Time Complexity O(n). We visit every node in the tree.
Space Complexity O(n). The Call Stack takes O(n) memory.
Using simple recursion:
0. Problem
Every time we move left in the BST, the values have to be lower than the parent value, which we'll call high. And every time we move right, the values have to be higher than the parent value, which we'll call low.
Here's an example:
To solve this problem, we want to make a function that checks if the tree is valid.
It needs to have low and high as inputs.
1. Recursion
A node is a BST if it's value is between low and high, and if its children are BSTs.
2. Base case
Eventually, the recursion gets to a node that's null. In this case, a null node is a valid BST.
3. Code
To code this up, just combine the recursion and base case.
Time Complexity O(n). We step through every node in the tree.
Space Complexity O(n). The Call Stack might get n calls deep if the tree is unbalanced.