ntree.ai
ntree.aiValidate Binary Search Tree

Solutions

1. Check bounds

O(n) time | O(n) space

Intuition

We can traverse through the tree carrying the lowest and the greatest value a node is allowed to take.

Algorithm

  1. Traverse through the tree from the root with low and high variables holding no bounds at the start.
  2. Check the node value is between low and high, return false if it is not.
  3. Repeat the same for the left child with high changed to the node value.
  4. Repeat the same for the right child with low changed to the node value.
  5. Return true.
5
3
2
4
8
5 is between -∞ and ∞
1 / 6

Code

Recursive implementation

Code
Python
# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def isValidBST(root: TreeNode) -> bool:
    return valid(root, float('-inf'), float('inf'))


def valid(node: TreeNode, low: float, high: float) -> bool:
    if not node:
        return True
    if not low < node.val < high:
        return False
    return valid(node.left, low, node.val) and valid(node.right, node.val, high)
// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {boolean}
 */
var isValidBST = function (root) {
  return valid(root, -Infinity, Infinity)
}

function valid(node, low, high) {
  if (!node) return true
  if (node.val <= low || node.val >= high) return false
  return valid(node.left, low, node.val) && valid(node.right, node.val, high)
}
// Definitions:
// 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 valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean valid(TreeNode node, long low, long high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;
        return valid(node.left, low, node.val) && valid(node.right, node.val, high);
    }
}

Iterative implementation

Code
Python
# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def isValidBST(root: TreeNode) -> bool:
    stack = [(root, float('-inf'), float('inf'))]
    while stack:
        node, low, high = stack.pop()
        if not node:
            continue
        if not low < node.val < high:
            return False
        stack.append((node.left, low, node.val))
        stack.append((node.right, node.val, high))
    return True
// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {boolean}
 */
var isValidBST = function (root) {
  const stack = [[root, -Infinity, Infinity]]
  while (stack.length) {
    const [node, low, high] = stack.pop()
    if (!node) continue
    if (node.val <= low || node.val >= high) return false
    stack.push([node.left, low, node.val])
    stack.push([node.right, node.val, high])
  }
  return true
}
// Definitions:
// 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;
//     }
// }

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private record Bound(TreeNode node, long low, long high) {}

    public boolean isValidBST(TreeNode root) {
        Deque<Bound> stack = new ArrayDeque<>();
        stack.push(new Bound(root, Long.MIN_VALUE, Long.MAX_VALUE));
        while (!stack.isEmpty()) {
            Bound at = stack.pop();
            if (at.node() == null) continue;
            if (at.node().val <= at.low() || at.node().val >= at.high()) return false;
            stack.push(new Bound(at.node().left, at.low(), at.node().val));
            stack.push(new Bound(at.node().right, at.node().val, at.high()));
        }
        return true;
    }
}

2. In Order Traversal

O(n) time | O(n) space

Intuition

We can traverse through the tree with in-order traversal. If the tree is a valid binary search tree, the values come in increasing order.

Algorithm

  1. Traverse through the tree in order: the left subtree, then the node, then the right subtree.
  2. Check every value is greater than the one before it, return false if it is not.
  3. Return true.
5
3
2
4
8
take 2
1 / 6

Code

Recursive implementation

Code
Python
# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def isValidBST(root: TreeNode) -> bool:
    values = []
    in_order(root, values)
    for i in range(1, len(values)):
        if values[i] <= values[i - 1]:
            return False
    return True


def in_order(node: TreeNode, values: list[int]) -> None:
    if not node:
        return
    in_order(node.left, values)
    values.append(node.val)
    in_order(node.right, values)
// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {boolean}
 */
var isValidBST = function (root) {
  const values = []
  inOrder(root, values)
  for (let i = 1; i < values.length; i++) {
    if (values[i] <= values[i - 1]) return false
  }
  return true
}

function inOrder(node, values) {
  if (!node) return
  inOrder(node.left, values)
  values.push(node.val)
  inOrder(node.right, values)
}
// Definitions:
// 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;
//     }
// }

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        inOrder(root, values);
        for (int i = 1; i < values.size(); i++) {
            if (values.get(i) <= values.get(i - 1)) return false;
        }
        return true;
    }

    private void inOrder(TreeNode node, List<Integer> values) {
        if (node == null) return;
        inOrder(node.left, values);
        values.add(node.val);
        inOrder(node.right, values);
    }
}

Iterative implementation

Code
Python
# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def isValidBST(root: TreeNode) -> bool:
    stack = []
    node = root
    previous = None
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if previous is not None and node.val <= previous:
            return False
        previous = node.val
        node = node.right
    return True
// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {boolean}
 */
var isValidBST = function (root) {
  const stack = []
  let node = root
  let previous = null
  while (stack.length || node) {
    while (node) {
      stack.push(node)
      node = node.left
    }
    node = stack.pop()
    if (previous !== null && node.val <= previous) return false
    previous = node.val
    node = node.right
  }
  return true
}
// Definitions:
// 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;
//     }
// }

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        Long previous = null;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if (previous != null && node.val <= previous) return false;
            previous = (long) node.val;
            node = node.right;
        }
        return true;
    }
}
# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None, parent=None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.parent = parent
 
def isValidBST(root: TreeNode) -> bool:
    pass
 

Press Visualise to step through your code.