- k == num_elements(left subtree of T) +1, then the answer we're looking for is the value in node T
- k > num_elements(left subtree of T) then obviously we can ignore the left subtree, because those elements will also be smaller than the
k
th smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T)
smallest element of the right subtree. - k < num_elements(left subtree of T), then the
k
th smallest is somewhere in the left subtree, so we reduce the problem to finding the k
th smallest element in the left subtree.
public class KthSmallestElement {
private static Node root;
public static void main(String[] args) {
int[] A = { 8, 3, 10, 1, 6, 14, 4, 7, 13 };
root = buildBST(root, A);
System.out.println("inorder: ");
printBSTInorder(root);
System.out.println();
int sizeBST = sizeOfBST(root);
System.out.println("Size of BST: " + sizeBST);
for (int i = 1; i <= sizeBST; i++) {
Node node = kthSmallestNode(root, i);
System.out.println(i + " largest node: " + node.data);
}
}
public static Node kthSmallestNode(Node node, int k) {
if (null == node) {
return null;
}
int r = sizeOfBST(node.left) + 1;
if (k == r) {
return node;
}
if (k < r) {
return kthSmallestNode(node.left, k);
} else {
return kthSmallestNode(node.right, k - r);
}
}
public static int sizeOfBST(Node node) {
if (null == node) {
return 0;
}
return (sizeOfBST(node.left) + 1 + sizeOfBST(node.right));
}
public static Node buildBST(Node node, int[] A) {
if (A == null) {
return null;
}
int len = A.length;
for (int i = 0; i < len; i++) {
node = insertIntoBST(node, A[i]);
}
return node;
}
private static Node insertIntoBST(Node node, int value) {
if (null == node) {
return new Node(value);
}
if (value <= node.data) {
node.left = insertIntoBST(node.left, value);
} else {
node.right = insertIntoBST(node.right, value);
}
return node;
}
public static void printBSTInorder(Node node) {
if (null == node) {
return;
}
if (null != node.left) {
printBSTInorder(node.left);
}
System.out.print(node.data + " ");
if (null != node.right) {
printBSTInorder(node.right);
}
}
}
class Node {
Integer data;
Node left;
Node right;
public Node(Integer data) {
this.data = data;
this.left = null;
this.right = null;
}
}
No comments:
Post a Comment