|
|
| Line 1: |
Line 1: |
| − | Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. There are 3 cases (I am assuming the index is 0-based):
| + | #REDIRECT [[UNTV]] |
| − | | |
| − | # index is equal to the left tree's size => This value is the ith node in sorted order | |
| − | # index is less than the left tree's size => The ith node is in the left tree
| |
| − | # index is greater than the left tree's size + 1 => The ith node is in the right tree
| |
| − | | |
| − | The implementation below only defines the methods required to answer this question, but clearly a full implementation of a binary search tree would need to have more.
| |
| − | | |
| − | <source lang="java">
| |
| − | import java.util.Optional;
| |
| − | | |
| − | public class BinarySearchTree {
| |
| − | private Optional<BinarySearchTree> left;
| |
| − | private Optional<BinarySearchTree> right;
| |
| − | private int value;
| |
| − | private int size;
| |
| − | | |
| − | public BinarySearchTree(final int value, final Optional<BinarySearchTree> left, final Optional<BinarySearchTree> right) {
| |
| − | this.value = value;
| |
| − | this.left = left;
| |
| − | this.right = right;
| |
| − | this.size = getLeftSize() + getRightSize() + 1;
| |
| − | }
| |
| − | | |
| − | private Integer getRightSize() {
| |
| − | return this.right.map(r -> r.size).orElse(0);
| |
| − | }
| |
| − | | |
| − | private Integer getLeftSize() {
| |
| − | return this.left.map(l -> l.size).orElse(0);
| |
| − | }
| |
| − | | |
| − | public int findIthNodeInSortedOrder(final int index) {
| |
| − | if (index < 0) {
| |
| − | throw new ArrayIndexOutOfBoundsException("Index cannot be less than 0");
| |
| − | }
| |
| − | | |
| − | if (index >= size) {
| |
| − | throw new ArrayIndexOutOfBoundsException("Index cannot be greater than or equal to size");
| |
| − | }
| |
| − | | |
| − | if (index == getLeftSize()) {
| |
| − | return value;
| |
| − | } else if (index < getLeftSize()) {
| |
| − | return left.get().findIthNodeInSortedOrder(index);
| |
| − | } else {
| |
| − | return right.get().findIthNodeInSortedOrder(index - (getLeftSize() + 1));
| |
| − | }
| |
| − | }
| |
| − | }
| |
| − | </source>
| |
