CODEWITHSUNDEEP
javaalgorithmbinary-search-tree
Liondancer
Liondancer

Reputation: 16469

printing largest n values in binary search tree

I am trying to create a method to print out the largest n values in a binary search tree. I was considering altering a reverse order print method to achieve this.

reverse order print method:

public static void reverseOrderPrint(TreeNode node) {
    if (node == null) return;
    reverseOrderPrint(node.right);
    System.out.println(node.data);
    reverseOrderPrint(node.right);
}

I wanted to modify the method above to something like this to achieve my goals

// print BST reverse Order
public static void reverseOrder(TreeNode node, int n) {
    if (sizeOfBinaryTree(node) < n) {
        System.out.print("n is bigger than tree");
        return;
    }
    if (node == null) return;
    reverseOrder(node.right);
    System.out.print(node.data);
    reverseOrder(node.left);
}

I have considered storing the reverse order elements in an array and then returning the first n values but this would have a performance of O(n) and require extra memory. How can I perform the same task recursively without requiring extra memory? Also is this possible to complete this problem in O(log n)? or does it have to be O(n)?

Upvotes: 2

Views: 2552

Answers (2)

codelion
codelion

Reputation: 1066

Update your method to below and it will print the largest n values. You can move the test for n bigger than tree outside the method. Call initially with i=0;

// print BST reverse Order
public static void reverseOrder(TreeNode node, int n,int i) {
    if (node == null) return;
        reverseOrder(node.right,n,i);
        if(++i<n) System.out.print(node.data);
        reverseOrder(node.left,n,i);
    }
}

Upvotes: 1

Arvind
Arvind

Reputation: 478

I think if you use Order Statistics on a Binary Search Tree, you can get the kth smallest element in O(logn)

Once you know which element is in the 'kth ' position, you can use normal Inorder Traversal, and print all elements greater than that number. So, this would avoid the extra O(n) storage.

Upvotes: 1

Related Questions