Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Move from brute-force thinking to an efficient approach using tree strategy.
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
Example 1:
Input: root = [2,1,3] Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
[1, 104].-231 <= Node.val <= 231 - 1Problem summary: Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys strictly less than the node's key. The right subtree of a node contains only nodes with keys strictly greater than the node's key. Both the left and right subtrees must also be binary search trees.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
[2,1,3]
[5,1,4,null,null,3,6]
binary-tree-inorder-traversal)find-mode-in-binary-search-tree)class Solution {
public boolean isValidBST(TreeNode root) {
return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean dfs(TreeNode node, long low, long high) {
if (node == null) return true;
if (node.val <= low || node.val >= high) return false;
return dfs(node.left, low, node.val) && dfs(node.right, node.val, high);
}
}
func isValidBST(root *TreeNode) bool {
var dfs func(node *TreeNode, low, high int64) bool
dfs = func(node *TreeNode, low, high int64) bool {
if node == nil {
return true
}
v := int64(node.Val)
if v <= low || v >= high {
return false
}
return dfs(node.Left, low, v) && dfs(node.Right, v, high)
}
return dfs(root, -(1<<63), (1<<63)-1)
}
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(node: Optional[TreeNode], low: int, high: int) -> bool:
if not node:
return True
if not (low < node.val < high):
return False
return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)
return dfs(root, float('-inf'), float('inf'))
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
let mut cur = root;
let mut prev: Option<i32> = None;
while cur.is_some() || !stack.is_empty() {
while let Some(node) = cur {
cur = node.borrow().left.clone();
stack.push(node);
}
let node = stack.pop().unwrap();
let val = node.borrow().val;
if let Some(p) = prev {
if val <= p {
return false;
}
}
prev = Some(val);
cur = node.borrow().right.clone();
}
true
}
}
function isValidBST(root: TreeNode | null): boolean {
const dfs = (node: TreeNode | null, low: number, high: number): boolean => {
if (!node) return true;
if (!(low < node.val && node.val < high)) return false;
return dfs(node.left, low, node.val) && dfs(node.right, node.val, high);
};
return dfs(root, -Infinity, Infinity);
}
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.