In this post we will solve the LeetCode 669 Trim a Binary Search Tree problem. This problem is ranked a Medium by LeetCode. It took me some extra time to figure out what I had to do.
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. Constraints: o The number of nodes in the tree in the range [1, 10^4]. o 0 <= Node.val <= 10^4 o The value of each node in the tree is unique. o root is guaranteed to be a valid binary search tree. o 0 <= low <= high <= 10^4 Related Topics: o Tree o Depth-First Search o Binary Search Tree o Binary Tree
The problem clearly states that we are presented with a binary search tree which specifies the relationship between node values.
We are also given two integers which describe a range of values. From that point on I had a hard time understanding what was required of the function of interest.
If this problem calls your attention, I suggest that you visit the LeetCode site and read the current description for this problem. Not sure if the requirements may change with time and you do not want to miss changes that could make the requirements easier to understand.
I developed the solution using the Java programming language and the VSCode IDE on a Windows platform. When needed I would copy and paste my code into the online IDE provided by LeetCode to submit it for evaluation. Given this, I had to develop a test scaffold that would read three input lines, allocate the necessary variables, pass them as arguments to the function of interest, read back the resulting binary tree and display it. Please note that if you use the online IDE provided by LeetCode the test scaffold WILL NOT BE REQUIRED!
/**
* 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) {
}
}
The signature for the function of interest has three arguments. We need a binary search tree, and the low and high values which specify the values for the nodes that we should not trim from the tree.
The TreeNode class is provided for us to be able to manipulate the binary search tree.
1,0,2 1 2 main <<< strArr.length: 3 main <<< strArr: [1, 0, 2] main <<< high: 2 main <<< low: 1 main <<< arr: [1, 0, 2] main <<< bst.inOrder: 0 1 2 main <<< bst.preOrder: 1 0 2 main <<< bst.levelOrderTraversal: [[1], [0, 2]] <<< val: 1 stays <<< val: 0 needs to be removed <<< val: 2 stays main <<< bst.levelOrderTraversal: [[1], [2]] 3,0,4,null,2,null,null,1 1 3 main <<< strArr.length: 8 main <<< strArr: [3, 0, 4, null, 2, null, null, 1] main <<< high: 3 main <<< low: 1 main <<< arr: [3, 0, 4, null, 2, null, null, 1] main <<< bst.inOrder: 0 1 2 3 4 main <<< bst.preOrder: 3 0 2 1 4 main <<< bst.levelOrderTraversal: [[3], [0, 4], [2], [1]] <<< val: 3 stays <<< val: 0 needs to be removed <<< val: 2 stays <<< val: 1 stays <<< val: 4 needs to be removed main <<< bst.levelOrderTraversal: [[3], [2], [1]] 1 1 2 main <<< strArr.length: 1 main <<< strArr: [1] main <<< high: 2 main <<< low: 1 main <<< arr: [1] main <<< bst.inOrder: 1 main <<< bst.preOrder: 1 main <<< bst.levelOrderTraversal: [[1]] <<< val: 1 stays main <<< bst.levelOrderTraversal: [[1]] 1,null,2 1 3 main <<< strArr.length: 3 main <<< strArr: [1, null, 2] main <<< high: 3 main <<< low: 1 main <<< arr: [1, null, 2] main <<< bst.inOrder: 1 2 main <<< bst.preOrder: 1 2 main <<< bst.levelOrderTraversal: [[1], [2]] <<< val: 1 stays <<< val: 2 stays main <<< bst.levelOrderTraversal: [[1], [2]] 2,1,8,null,null,6,9,5,7 5 7 main <<< strArr.length: 9 main <<< strArr: [2, 1, 8, null, null, 6, 9, 5, 7] main <<< high: 7 main <<< low: 5 main <<< arr: [2, 1, 8, null, null, 6, 9, 5, 7] main <<< bst.inOrder: 1 2 5 6 7 8 9 main <<< bst.preOrder: 2 1 8 6 5 7 9 main <<< bst.levelOrderTraversal: [[2], [1, 8], [6, 9], [5, 7]] <<< val: 2 needs to be removed <<< val: 8 needs to be removed <<< val: 6 stays <<< val: 5 stays <<< val: 7 stays main <<< bst.levelOrderTraversal: [[6], [5, 7]] 1,null,2 2 4 main <<< strArr.length: 3 main <<< strArr: [1, null, 2] main <<< high: 4 main <<< low: 2 main <<< arr: [1, null, 2] main <<< bst.inOrder: 1 2 main <<< bst.preOrder: 1 2 main <<< bst.levelOrderTraversal: [[1], [2]] <<< val: 1 needs to be removed <<< val: 2 stays main <<< bst.levelOrderTraversal: [[2]] 3,0,5,null,2,4,null,1,null 1 3 main <<< strArr.length: 9 main <<< strArr: [3, 0, 5, null, 2, 4, null, 1, null] main <<< high: 3 main <<< low: 1 main <<< arr: [3, 0, 5, null, 2, 4, null, 1, null] main <<< bst.inOrder: 0 1 2 3 4 5 main <<< bst.preOrder: 3 0 2 1 5 4 main <<< bst.levelOrderTraversal: [[3], [0, 5], [2, 4], [1]] <<< val: 3 stays <<< val: 0 needs to be removed <<< val: 2 stays <<< val: 1 stays <<< val: 5 needs to be removed <<< val: 4 needs to be removed main <<< bst.levelOrderTraversal: [[3], [2], [1]]
A test case is separated from others by two blank lines.
The first three lines in a test case represent the input lines. The first line holds the values for the tree in a level order traversal format. This is quite a standard for LeetCode. I like consistency. The next line holds the value for the `low` value in the range, and the third line the value for the `high` in the range.
It appears that our test code displays the length of an array holding the values for the nodes in the binary search tree. The contents for what appears to be a String array holding the values for the nodes is then displayed. The contents of the `low` and `high` variables follows.
It appears that the int[] named `arr` holds the same contents as the `strArr` after having been converted to binary.
Our test code seems to create and populate the binary search tree.
The new three lines display different tree traversals of the specified binary tree. The first is an in-order order traversal, the second and pre-order traversal, and the third a level order traversal. I used these different representations to make sure all was well before calling the function of interest. Hopefully you can follow the Test Driven Development approach I like to use to solve problems.
The next few lines seem to be generated by the function of interest.
The last line represents the trimmed binary search tree returned by the function of interest.
Conditions: o When the root is less than low answer is root.right o When the root is greater tahn high answer is root.left o When root is in range answer is root
The idea is to visit each node in the binary search tree using a pre-order traversal algorithm. For each node we need to decide how to proceed. This will become cleared after we take a look at the code for the function of interest.
/**
* Test scaffold.
*
* !!! NOT PART OF SOLUTION !!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** create String[] with values for the BST ****
String[] strArr = br.readLine().trim().split(",");
// **** read low ****
int low = Integer.parseInt(br.readLine().trim());
// **** read high ****
int high = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr.length: " + strArr.length);
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
System.out.println("main <<< high: " + high);
System.out.println("main <<< low: " + low);
// **** generate an Integer[] to build the binary tree ****
Integer[] arr = new Integer[strArr.length];
for (int i = 0; i < strArr.length; i++) {
if (strArr[i].equals("null") || strArr[i].isEmpty())
arr[i] = null;
else
arr[i] = Integer.parseInt(strArr[i]);
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create and populate the binary serach tree ****
BST bst = new BST();
bst.root = bst.populate(arr);
// ???? ????
System.out.println("main <<< bst.inOrder: " + bst.inOrder(bst.root));
System.out.println("main <<< bst.preOrder: " + bst.preOrder(bst.root));
// ???? ????
System.out.print("main <<< bst.levelOrderTraversal: ");
System.out.println(bst.levelOrderTraversal(bst.root).toString());
// **** call function of interest ****
TreeNode trimmed = trimBST(bst.root, low, high);
// **** display level order traversal of trimmed BST ****
System.out.print("main <<< bst.levelOrderTraversal: ");
System.out.println(bst.levelOrderTraversal(trimmed).toString());
}
The test scaffold seems to follow the description of the test cases.
After populating the int[] `arr` the code calls a function to create and populate the associated binary search tree. Please note that such a call IS NOT PART OF THE SOLUTION!
To verify that the binary search tree is properly populated, we make some calls to perform and display some tree traversals. Please note that such code IS NOT PART OF THE SOLUTION!
Finally the function of interest is called with the specified arguments and a `trimmed` binary search tree is returned. This time we just display the results of a level order tree traversal.
/**
* 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].
*
* Depth first search pre-order traversal.
*
* Execution: O(n) - Space: O(1)
*
* 78 / 78 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.3 MB
*/
static public TreeNode trimBST(TreeNode root, int low, int high) {
// **** base case ****
if (root == null) return null;
// ???? ????
System.out.print("<<< val: " + root.val);
if (root.val >= low && root.val <= high)
System.out.println(" stays");
else
System.out.println(" needs to be removed");
// // **** return trim of right child ****
// if (root.val < low) {
// return trimBST(root.right, low, high);
// }
// // **** return trim of left child ****
// else if (root.val > high) {
// return trimBST(root.left, low, high);
// }
// // **** recurse on left and right children ****
// else {
// // **** trim root left child ****
// root.left = trimBST(root.left, low, high);
// // **** trim root right child ****
// root.right = trimBST(root.right, low, high);
// }
// **** recurse on left and right children ****
if (root.val >= low && root.val <= high) {
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
}
// **** replace root with right child ****
else if (root.val < low) {
return trimBST(root.right, low, high);
}
// **** replace root with left child ****
else if (root.val > high) {
return trimBST(root.left, low, high);
}
// **** return root ****
return root;
}
The solution is based on a modified preorder tree traversal using recursion.
We start by testing the base case condition.
Please disregard the code commented out. It is harder to follow due to the fact that it was developed while debugging the code.
The set of conditions represent a preorder binary tree traversal. If we do not have to trim this node, then we need to check if we trim the left and the right children.
We then check if we need to replace this node. Note that if the value for the node is lower than the `low` value, we need to proceed using the right child. If we encounter the condition that the node value is larger than the value in the `high` argument, we need to proceed with the left child. Note that in both situations we need to trim / remove the node that we are visiting. If needed please look at some of the examples, draw the associated tree representations, and then step through the code.
The problem is more palatable after you figure out what is required from the function of interest. It took me a while to get to the solution. What can I say?
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named TrimABinaryTree. It includes the classes to manipulate the binary search trees.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John