Nehorai - 1 year ago 60
Java Question

function that returns the k-th value in binary search tree

I need to write a function that returns the k-ith value in his size in binary search tree

e.g if this is the binary search tree:

``````                                  50
/  \
46    58
/ \    / \
32  48  53  67
``````

then if k=3 so the function should return 48

because 48 is in the third place in his size.

32,46,48,50,53,58,67.

My idea is to use inorder somehow but I'm stuck a lot of hours, I don't think that it should be hard, I need a pseudo code or a better code then mine please.

here is what I did in JAVA eclipse:

``````private static void k_val_inorder(TreeItem x,int k)
{
if (x != null&&k!=0)
{
k_val_inorder(x.getLeft(),k--);
System.out.print(x.getKey()+" ");
k_val_inorder(x.getRight(),k--);
}

}
``````

Given TreeNode class to implement a binary tree:

``````public class TreeNode {
int data;
TreeNode left;
TreeNode right;

TreeNode(int data) {
this.data = data;
}
}
``````

Infix traversal for a given binary tree:

``````public void inFix(TreeNode root, List<Integer> inFixRep) {
if (root != null) {
inFix(root.left, inFixRep);
The above method populates a `List<Integer>`. This list contains the infix representation of the given binary tree. To get the k-th node, just get the (k-1)th element of the list like `inFixRep.get(k-1)`.