Big O Gym › Problem

Big O Practice: Validate Bst

Time and space complexity practice in Python and JavaScript. Concept tested: tree recursion with bounds carried in args.

INF = float('inf')

def is_valid_bst(node, lo=-INF, hi=INF):
    if not node:
        return True
    if not (lo < node.val < hi):
        return False
    return (is_valid_bst(node.left, lo, node.val) and
            is_valid_bst(node.right, node.val, hi))

Variables

  • n - number of nodes in the tree
  • h - height of the tree

Explanation

Each node is checked once with O(1) bounds work - **O(n)** time. Recursion depth is the tree height **O(h)** - `log n` balanced, `n` skewed.

More Big O practice problems · Today's daily problem