beingsde
Sign In
Back to all DSA patterns
Tree•Pattern: DFS with Bounds•Medium

Validate a Binary Search Tree

Problem Intuition & Objective

Determine if a binary tree is a valid BST.

Time ComplexityO(n)
Optimal
Space ComplexityO(h) recursion stack
Memory Bounds
Optimal Algorithmic Approach

Range-bounded DFS: pass min/max bounds down the recursion.

Core Invariants & Edge Cases

  • Track valid range [min, max] for each node, not just compare with parent
  • Left subtree max is bounded by current node's value; right by a minimum
  • In-order traversal should yield strictly increasing values
Previous ProblemBinary tree level-order traversal (BFS)Next Problem Lowest Common Ancestor (LCA) of a binary tree

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.