Last active
August 29, 2015 14:14
-
-
Save dmnugent80/acf1f3c316a6fce7e98c to your computer and use it in GitHub Desktop.
Binary Search Tree Print Kth Element
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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