Nehorai - 1 year ago 39

Java Question

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)`

.

Source (Stackoverflow)