Warm tip: This article is reproduced from stackoverflow.com, please click
binary-search-tree data-structures java

Trim Binary Search Tree Using Recursion

发布于 2020-03-27 10:17:35

TRIM BST Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

I am a newbie and just started learning recursion .. i wrote the code as written below . It works some some of the test cases and gives Null Pointer exception for the rest. I know the solution of the problem (also written below) but i want to fix my code instead of writing the way the solution is written.

here is my attempt.

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
    if(root==null)
    {
        return root;
    }
    if(root.val<L)
    {
        root=root.right;
        if(root==null)
        {
            return root;
        }
    }
     if(root.val>R)
    {
        root=root.left;
          if(root==null)
        {
            return root;
        }
    }
     if(root.left!=null)
    {
        if(root.left.val<L)
        {
            root.left=root.left.right;
        }

    }
     if(root.right!=null)
    {
        if(root.right.val>R)
        {
            root.right=root.right.left;
        }

    }
    trimBST(root.left,L,R);
    trimBST(root.right,L,R);
    return root;

}
}

gives error for

    [3,1,4,null,2]
3
4

here is the solution

class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return root;
        if (root.val > R) return trimBST(root.left, L, R);
        if (root.val < L) return trimBST(root.right, L, R);

        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}

i know i have messed up somewhere in the recursion code and have made a value null and again using it and i feel that i am very close to the solution. I am not able to figure that out on my own. Please Help Me out.

Questioner
Mridul Mittal
Viewed
142
mnestorov 2019-07-03 21:30

The reason it's not working for you in this case is that, at the end you need to recursively get the new root. That is, trimBST(root.left, L, R); will recursively go down the tree, but it will return to nothing in the end. So you will need to assign it to either the left or right side of the tree.

root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);

But you will also have another problem after that, connected with root=root.right; and root=root.left;. As a hit, you have to use recursion here as well.