Nehorai 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:

/ \
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.


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)
System.out.print(x.getKey()+" ");


any ideas please?

Answer Source

Given TreeNode class to implement a binary tree:

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

    TreeNode(int data) { = data;

Infix traversal for a given binary tree:

public void inFix(TreeNode root, List<Integer> inFixRep) {
    if (root != null) {
        inFix(root.left, inFixRep);
        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).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download