java binary search tree finding second smallest node

Question

I am trying to make the method find the second smallest node However, when I found the smallest node(which doesn't have right node) I should return the parent of the node to make it "second" smallest. However, I don't have an idea to make it like that... please help me out guys

public StringNode secondSmallest() {
    return secondSmallest(root);
}

private StringNode secondSmallest(StringNode x) {
    if(x==null);
    //base case: if the left node is null -> smallest
    if (x.getLeft()==null) {        
        //if there is only right child
        if(x.getRight()!=null) {
            return x.getRight();
        }
        //when there is no right node and smallest
        return x;
    }
    //keep finding left node
    else
        return secondSmallest(x.getLeft());

}

Your version traverses all the way down the left side, and then returns an element no matter what. This doesn't work because it doesn't follow the invariants of a BST. Are you familiar with [in-order traversal](https://en.wikipedia.org/wiki/Tree_traversal#In-order_.28symmetric.29)? — mkobit, Sep 21 '15 at 04:15
Thank you for your comment. I am currently learning about BST in my school. Can you explain little about it? If you can — IAMBEAST, Sep 21 '15 at 05:42

score 2 · Accepted Answer · answered Sep 21 '15 at 05:56

2

Sample code.

public interface Tree<K, V> {
       /**
     * Find the nth smallest element in the tree
     * 
     * @param nth
     * @return nth smallest element in the tree
     */
    public K findSmallest(int nth);
}

@Override


 public K findSmallest(int nth) {
    Node iterator = root;
    return traverseLeftParentRight(iterator, new AtomicInteger(nth));
  }



private K traverseLeftParentRight(Node iterator, AtomicInteger nth) {
    if (null == iterator || nth.get() == 0) {
      return null;
    }
    K value = traverseLeftParentRight(iterator.left, nth);
    // Found in the left subtree itself
    if (null != value) {
      return value;
    }
    if (nth.decrementAndGet() == 0) {
      return iterator.key;
    }
    // Check in the right subtree
    return traverseLeftParentRight(iterator.right, nth);
  }



  public static void main(String[] args) {
      // Create a BST
      Comparator comparator = integerComparator();
      Tree tree = new BinarySearchTree(comparator);
      fillData(tree);
      System.out.println("4thlest element " + tree.findSmallest(4));
   }

private static void fillData(Treetree) {
  tree.put(5, "value-5");
  for (int i = 0; i <= 10; i++) {
   tree.put(i, "value-" + i);
  }
 }

Read this Nth Samllest Element article for complete details.

answered Sep 21 '15 at 05:56

Ravindra babu

37,698
11
250
211

Found one more solution in SE: http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way/2329236#2329236 – Ravindra babu Sep 21 '15 at 05:58
I think this isn't what I am looking for, I like to make a method only take one parameter "(Node x)" and use recursive way to find out the second left minimum value. `if (nth.decrementAndGet() == 0) { return iterator.key; }` I don't get it this part too – IAMBEAST Sep 21 '15 at 06:04
Look at "Amazon I'm coming" solution in http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way/2329236#2329236. You have to pass 2nd parameter too to know Nth smallest element. Pass N as 2 to get second smallest – Ravindra babu Sep 21 '15 at 06:29
1

the integer should be AtomicInteger? or It can be regular integer? – IAMBEAST Sep 21 '15 at 23:14
you will pass normal integer. This integer is converted to AtomicInteger in public K findSmallest(int nth) { Node iterator = root; return traverseLeftParentRight(iterator, new AtomicInteger(nth)); } – Ravindra babu Sep 22 '15 at 06:48
Did you get any error with this code? Share your issues. – Ravindra babu Sep 22 '15 at 21:00
not yet, I think it's really good though.. sorry for late check as the answer. – IAMBEAST Sep 23 '15 at 04:14

java binary search tree finding second smallest node

1 Answers1