Good morning! Here's our prompt for today.

Given a binary search tree like the one below, can you write a function that will return true if it is valid?

1    5 
2   / \ 
3  3   9 
4 / \
51   4

Recall that a BST is valid only given the following conditions:

• The left child subtree of a node contains only nodes with values less than the parent node's.
• The right child subtree of a node contains only nodes with values greater than the parent node's.
• Both the left and right subtrees must also be BSTs.

You can assume that all nodes, including the root, fall under this node definition:

1class Node {
2	constructor(val) {
3		this.value = val;
4		this.left = null;
5		this.right = null;
6	}
7}

The method may be called like the following:

1root = new Node(5);
2root.left = new Node(3);
3root.right = new Node(9);
4
5console.log(isValidBST(root));

Constraints

• Length of the given tree <= 100000
• The nodes in the tree will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(logn) or O(d) where d is the depth of the tree

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

def is_valid_bst(root):

    # fill in

    return True

​

​

# Node definition

class Node:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

​

​

# Regular binary trees

tree1 = Node(4)

tree1.left = Node(1)

tree1.right = Node(3)

​

tree2 = Node(5)

tree2.left = Node(10)

tree2.left.left = Node(17)

tree2.left.right = Node(3)

tree2.right = Node(8)

​

# Binary search trees

tree3 = Node(6)

tree3.left = Node(3)

​

tree4 = Node(5)

Here's our guided, illustrated walk-through.

How do I use this guide?

Inputs and outputs

Let's start, as always, with a few examples. Running through some inputs helps our brains to intuit some patterns. This may help trigger an insight for a solution.

Let's say we just have this simple binary search tree:

xxxxxxxxxx

/*

​

  5 

 / \ 

3   9 

​

*/

Is this valid? It sure seems so, the first criteria that comes to mind being that 3 is less than 5, and therefore that node is to the left. On the other hand, 9 is greater than 5, and thus is to the right. Alright, this seems like a no brainer, let's just check that every left child is smaller than the root, and every right child is greater than the local root.

Brute force solution?

Here's a possible early solution:

xxxxxxxxxx

function isValidBST(root) {

  if (root.left < root.val && root.right > root.val) {

    return true;

  }

}

We should be able to run through that method recursively, and check every subtree. Is that enough though? Let's extend our tree a bit and add two more children to the root's left child.

xxxxxxxxxx

/*

​

    5 

   / \ 

  3   9 

 / \

2   8

​

*/

Is the above a valid binary search tree? It is not -- if our root is 5, the entire left subtree (with 3 as the root) needs to have keys less than the parent tree's root key. Notice that the 8 is still to the left of 5, which is invalidates the simple recursive function from above.

Pattern recognition

In thinking about what we need to do with this tree, there clearly needs to be some form of traversal so that we can check the nodes against each other.

Two questions we can ask are: 1. Is there a way to compare node values without, or possibly exclusive, of the traversal? 2. What technique or pattern can help us easily compare tree values?

The answer is an in-order depth-first search of the tree. As you'll recall, an in-order DFS follows the standard depth-first method of going as deep as possible on each child before going to a sibling node. However, the difference is, it will process all left subtree nodes first, do something with the root or current node, and then process all right subtree nodes.

Because of the definition of a binary search tree, valid ones will produce an in-order DFS traversal in sorted order from least to greatest.

Thus, we can use this to our advantage. Here's a simple inOrder method to run through a binary search tree and return a list of node values.

xxxxxxxxxx

function inOrder(root, output) {

  if (!root) {

    return;

  }

​

  inOrder(root.left, output);

  output.append(root.val);

  inOrder(root.right, output);

}

If this is in sorted order, we know that this is valid. We can check this iterating through the returned list, checking that each iterated element's value is greater than the previous iteration's. If we get to the end, we can return True. If the opposite is ever true, we'll immediately return False.

Complexity of Final Solution

Let n be the size of the tree. We traverse through all n tree nodes using recursion for O(n) time complexity, and we have O(logn) space complexity due to recursion or O(d) where d is the depth of the tree.