Find range in BST

By | January 27, 2015
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

This is a practice for Tree. The idea is to find all results in a certain range in BST.

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import util.Tree;
  4. public class FindRangeInBst {
  5.     public static void main(String[] args) {
  6.         Tree bst = Tree.getBst();
  7.         List<Tree> result = new ArrayList<Tree>();
  8.         findRangeInBst(bst, 11, 16, result);
  9.         System.out.println(result.toString());
  10.     }
  11.     public static void findRangeInBst(Tree tree, int min, int max,
  12.             List<Tree> result) {
  13.         if (tree == null) {
  14.             return;
  15.         }
  16.         if (tree.value >= min && tree.value <= max) {
  17.             result.add(tree);
  18.             findRangeInBst(tree.left, min, max, result);
  19.             findRangeInBst(tree.right, min, max, result);
  20.         } else if (tree.value < min) {
  21.             findRangeInBst(tree.right, min, max, result);
  22.         } else {
  23.             findRangeInBst(tree.left, min, max, result);
  24.         }
  25.     }
  26. }