Saturday, March 23, 2013

Kth Smallest Element in a binary search tree

  1. k == num_elements(left subtree of T) +1, then the answer we're looking for is the value in node T
  2. k > num_elements(left subtree of T) then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.
  3. k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth 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: