#669

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Trim a Binary Search Tree

Trim a Binary Search Tree by maintaining its structure while removing nodes outside a given range.

tree depth first search binary search tree binary tree

Problem Statement

You are given the root of a binary search tree (BST) and two boundary values, low and high. Your task is to trim the tree so that all the node values lie within the given range [low, high]. Any nodes outside this range should be removed, but the relative structure of the tree should be preserved.

The root of the tree may change as a result of trimming, but the resulting tree must maintain its properties as a binary search tree. The task requires performing an efficient traversal, ensuring that the tree is modified correctly without violating its binary search tree structure.

Examples

Example 1

Input: root = [1,0,2], low = 1, high = 2

Output: [1,null,2]

Example details omitted.

Example 2

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3

Output: [3,2,null,1]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 104
The value of each node in the tree is unique.
root is guaranteed to be a valid binary search tree.
0 <= low <= high <= 104

Solution Approach

Depth-First Search (DFS) Traversal

To solve this problem, a Depth-First Search (DFS) traversal can be employed. Starting from the root, we recursively traverse the tree, trimming nodes that fall outside the specified range. For each node, if it’s outside the bounds, we trim it and adjust the tree accordingly by returning the proper subtree.

Handling Tree Modification

During traversal, nodes that lie outside the range should be removed by reattaching the valid children of the node. If a node’s value is below the low boundary, its left child can be discarded, and we recursively continue the process for the right child. Similarly, if a node’s value is above the high boundary, the right child is discarded, and the left child is recursively processed.

Edge Case Considerations

When handling edge cases, it's important to consider situations like empty trees or trees where all nodes are outside the given range. The algorithm should be robust enough to handle cases where the entire tree is removed or when no nodes need to be trimmed.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of nodes, as we visit each node once. Hence, the time complexity is O(n), where n is the number of nodes in the tree. The space complexity is O(h), where h is the height of the tree, due to recursion stack usage during the DFS traversal.

What Interviewers Usually Probe

Evaluates understanding of tree traversal techniques like DFS.
Tests ability to modify the tree while maintaining binary search tree properties.
Assesses problem-solving skills in handling edge cases and large input sizes.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the impact of trimming on tree structure, leading to incorrect child node connections.
Incorrectly handling edge cases, such as an empty tree or a tree where all nodes fall outside the range.
Not maintaining the binary search tree property after trimming the tree.

Follow-up variants

Trimming with different range boundaries, such as low = 0 and high = 10, testing the ability to handle various boundary values.
Trimming a more complex tree with a larger number of nodes, increasing the challenge in tree traversal and modification.
Handling trees where all nodes are within the specified range, ensuring no unnecessary trimming occurs.

FAQ

What is the main challenge in trimming a binary search tree?

The main challenge is efficiently trimming the tree while maintaining its binary search tree properties, ensuring the structure remains valid after removal of out-of-range nodes.

How do I handle nodes that lie outside the given range?

You discard nodes outside the range by adjusting the tree structure, either removing left or right children based on whether the node is too small or too large.

What traversal technique should I use to trim a binary search tree?

A Depth-First Search (DFS) traversal is ideal for this problem, as it allows you to process each node recursively and adjust the tree accordingly.

How do I optimize my solution for large trees?

To optimize the solution for large trees, focus on efficient traversal and ensure that unnecessary operations are minimized. Also, consider iterative approaches to avoid deep recursion.

Can the root of the tree change after trimming?

Yes, the root of the tree may change after trimming if the original root node falls outside the specified range.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# 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)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# 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)

Continue Practicing

#653 two sum iv input is a bst #783 minimum distance between bst nodes #538 convert bst to greater tree