# 669. Trim a Binary Search Tree

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

# 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):
        return self.returnValidNode(root, low, high)

    def inRange(self, num, low, high):
        if num >= low and num <= high:
            return True
        else:
            return False

    def returnValidNode(self, root, low, high):
        if root is None:
            return root

        # Getting the first valid value of the current node
        # using BFS
        validQueue = [root]
        currentNode = None
        # while queue is not empty
        while validQueue:
            currentNode = validQueue.pop()
            if self.inRange(currentNode.val, low, high):
                # first element in queue is valid
                break
            else:
                # appending children to queue
                if currentNode.left is not None:
                    validQueue.append(currentNode.left)
                if currentNode.right is not None:
                    validQueue.append(currentNode.right)
            # when leaving the loop with empty queue
            if not validQueue:
                currentNode = None

        # if there is a current node
        if currentNode:
            # replace the children with the recursive values of the children
            currentNode.left = self.returnValidNode(currentNode.left, low,
                                                    high)
            currentNode.right = self.returnValidNode(currentNode.right, low,
                                                     high)
        return currentNode
