Trim a Binary Search Tree

Leetcode Problem 669: Trim a Binary Search Tree

Problem Summary

Given the root of a Binary Search Tree (BST) and bounds [low, high], trim the tree so that all node values lie within the range [low, high], preserving the original relative structure of the remaining nodes. Return the root of the trimmed tree (which may differ from the original root).

Constraints:

• The tree has between 1 and 10,000 nodes with unique values.
• Node values and bounds are non-negative integers up to 10,000.
• low <= high, and both are valid BST values.
• The tree is guaranteed to be a valid BST.

Techniques

• Tree
• Depth-First Search
• Binary Search Tree
• Binary Tree

Solution

export 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 {
    if (!root) {
        return null
    }

    if (root.val < low) {
        return trimBST(root.right, low, high)
    }

    if (root.val > high) {
        return trimBST(root.left, low, high)
    }

    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)

    return root
}