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 search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.
Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.
Example 1:
Input: root = [1,0,2], low = 1, high = 2 Output: [1,null,2]
Example 2:
Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3 Output: [3,2,null,1]
Constraints:
[1, 104].0 <= Node.val <= 104root is guaranteed to be a valid binary search tree.0 <= low <= high <= 104Problem summary: Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer. Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
[1,0,2] 1 2
[3,0,4,null,2,null,null,1] 1 3
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #669: Trim a Binary Search Tree
/**
* Definition for a binary tree node.
* public 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 TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) {
return root;
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
if (root.val < low) {
return trimBST(root.right, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
// Accepted solution for LeetCode #669: Trim a Binary Search Tree
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func trimBST(root *TreeNode, low int, high int) *TreeNode {
if root == nil {
return root
}
if root.Val > high {
return trimBST(root.Left, low, high)
}
if root.Val < low {
return trimBST(root.Right, low, high)
}
root.Left = trimBST(root.Left, low, high)
root.Right = trimBST(root.Right, low, high)
return root
}
# Accepted solution for LeetCode #669: Trim a Binary Search Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def trimBST(
self, root: Optional[TreeNode], low: int, high: int
) -> Optional[TreeNode]:
def dfs(root):
if root is None:
return root
if root.val > high:
return dfs(root.left)
if root.val < low:
return dfs(root.right)
root.left = dfs(root.left)
root.right = dfs(root.right)
return root
return dfs(root)
// Accepted solution for LeetCode #669: Trim a Binary Search Tree
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn trim_bst(
mut root: Option<Rc<RefCell<TreeNode>>>,
low: i32,
high: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
if root.is_none() {
return root;
}
{
let mut node = root.as_mut().unwrap().borrow_mut();
if node.val < low {
return Self::trim_bst(node.right.take(), low, high);
}
if node.val > high {
return Self::trim_bst(node.left.take(), low, high);
}
node.left = Self::trim_bst(node.left.take(), low, high);
node.right = Self::trim_bst(node.right.take(), low, high);
}
root
}
}
// Accepted solution for LeetCode #669: Trim a Binary Search Tree
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
const dfs = (root: TreeNode | null) => {
if (root == null) {
return root;
}
const { val, left, right } = root;
if (val < low || val > high) {
return dfs(left) || dfs(right);
}
root.left = dfs(left);
root.right = dfs(right);
return root;
};
return dfs(root);
}
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.