669. Trim a Binary Search Tree #

Problem #

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]

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

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

Problem Summary #

Given the root node root of a binary search tree, along with the minimum boundary low and maximum boundary high, trim the binary search tree so that the values of all nodes are in [low, high]. Trimming the tree should not change the relative structure of the elements retained in the tree (that is, if they are not removed, the original parent-child relationships should be preserved). It can be proven that there is a unique answer. Therefore, the result should return the new root node of the trimmed binary search tree. Note that the root node may change depending on the given boundaries.

Solution Approach #

• This problem tests recursive traversal in a binary search tree. Recursively traverse each node of the binary search tree. Based on the ordering property, if the current node is greater than high, then the entire right subtree of the current node is trimmed away, and then recursively trim the left subtree; if the current node is less than low, then the entire left subtree of the current node is trimmed away, and then recursively trim the right subtree. After handling the out-of-bound cases, all remaining cases are within the interval, so recursively trim the left subtree and right subtree respectively.

Code #

package leetcode

import (
	"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
 * 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
}