Skip to content

Instantly share code, notes, and snippets.

@dmnugent80
Last active August 29, 2015 14:14
Show Gist options
  • Save dmnugent80/acf1f3c316a6fce7e98c to your computer and use it in GitHub Desktop.
Save dmnugent80/acf1f3c316a6fce7e98c to your computer and use it in GitHub Desktop.
Binary Search Tree Print Kth Element
public class Main
{
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.add(5);
tree.add(4);
tree.add(6);
tree.add(3);
tree.add(7);
tree.add(2);
tree.add(8);
tree.add(1);
tree.add(9);
tree.printKthElement(7);
}
}
public class TreeNode
{
int data;
TreeNode left;
TreeNode right;
public TreeNode(int d){
data = d;
left = null;
right = null;
}
}
public class IntWrapper{
int value = 0;
}
public class BinaryTree
{
TreeNode root;
public BinaryTree(){
root = null;
}
public boolean add(int newData){
if (root == null){
root = new TreeNode(newData);
return true;
}
else{
TreeNode curr = root;
while (true){
if (curr.data == newData){
return false;
}
else if (curr.data > newData){
if (curr.left == null){
curr.left = new TreeNode(newData);
return true;
}
else{
curr = curr.left;
}
}
else{
if (curr.right == null){
curr.right = new TreeNode(newData);
return true;
}
else{
curr = curr.right;
}
}
}
}
}
public void printKthElement(int k){
IntWrapper elementCounter = new IntWrapper();
printKthElementHelper(root, k, elementCounter);
}
public void printKthElementHelper(TreeNode node, int k, IntWrapper counter){
if (node == null)
return;
printKthElementHelper(node.left, k, counter);
counter.value = counter.value + 1;
if (counter.value == k){
System.out.println("Kth Element: " + node.data);
}
printKthElementHelper(node.right, k, counter);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment