Nehorai Nehorai - 6 months ago 13
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--);
}

}


any ideas please?

Answer

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);
        inFixRep.add(root.data);
        inFix(root.right, 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).