Sunday, December 13, 2015

Find smallest larger element than target in BST

Question:
Given a BST:
                 10
        7                    14
    4      8      12              19
                         13     16    20
   
[4,7,8,10,12,13,14,16,19,20]

Q1.  Find smallest larger element than target,  
     Example: input: target = 13,  output: 14

Q2.  Find largest smaller element than target,  
     Example: input: target = 13,  output: 12


Answer:
public class Solution {

//Q1.  Find smallest larger element than target:           Time:O(logn), Space:O(1)
public static int findNLR(TreeNode root, int target, int min, int max) throws Exception{
              //if root.val > target, return the smallest element in the subtree
        if(root.val > target){
               if(root.left != null){
                            //go left branch
                      return findNLR(root.lefttargetminroot.val);
               }else{
                      return root.val;
                }
         }          
        else{
              if(root.right != null){
                          //go right branch
                     return findNLR(root.right, target, root.val, max);
              }else{
                      if(max != Integer.MAX_VALUE){
                             return max;
                     }
                     else{
                            throw new Exception();
                      }
              }
        }           
}
public static int findNL(TreeNode root, int target) throws Exception{
         return findNLR(root, target, Integer.MIN_VALUE, Integer.MAX_VALUE);
}


//Q2.  Find largest smaller element than target:               Time:O(logn), Space:O(1)
public static int findPSL(TreeNode rootint targetint minint maxthrows Exception{
                  //if root.val < target, return the largest element in the subtree
        if(root.val < target){
             if(root.right!=null){
                            //go right branch
                    return findPSL(root.righttargetroot.valmax);
             }else{
                    return root.val;
             }
        }
        else{
               if(root.left!=null){
                            //go left branch
                      return findPSL(root.lefttargetminroot.val);
               }else{
                      if(min != Integer.MIN_VALUE){
                            return min;
                      }
                      else{
                             throw new Exception();
                      }
               }
         }
}
public static int findPS(TreeNode rootint targetthrows Exception{
         return findPSL(roottarget, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

   
  public static void main(String[] args) throws Exception {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(7);
        root.right = new TreeNode(14);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(8);
        root.right.left = new TreeNode(12);
        root.right.left.right = new TreeNode(13);
        root.right.right = new TreeNode(19);
        root.right.right.left = new TreeNode(16);
        root.right.right.right = new TreeNode(20);
        int res = findNL(root, 13);
        System.out.println(res);   
   }
}

No comments:

Post a Comment