class BST
{ private static Node root; public static void main(String [] args) { int [] A = {8, 3, 10, 1, 6, 14, 4, 7, 13}; root = buildBST(root, A); System.out.println("inorder: "); printBSTInorder(root); System.out.println(); int sizeBST = sizeOfBST(root); System.out.println("Size of BST: " + sizeBST); for (int i=1; i<=sizeBST; i++) { Node node = nthLargestNode(root, i); System.out.println(i + " largest node: " + node.data); } } public static Node nthLargestNode(Node node, int N) { if (null == node) { return null; } int R = sizeOfBST(node.right) + 1; if (N == R) { return node; } if(N < R) { return nthLargestNode(node.right, N); } else { return nthLargestNode(node.right, N-R); } } public static int sizeOfBST(Node node) { if (null == node) { return 0; } return (sizeOfBST(node.left) + 1 + sizeOfBST(node.right)); } public static Node buildBST(Node node, int [] A) { if (A == null) { return null; } int len = A.length; for (int i=0; i<len; i++) { node = insertIntoBST(node, A[i]); } return node; } private static Node insertIntoBST(Node node, int value) { if (null == node) { return new Node(value); } if (value <= node.data) { node.left = insertIntoBST(node.left, value); } else { node.right = insertIntoBST(node.right, value); } return node; } public static void printBSTInorder(Node node) { if (null == node) { return ; } if (null != node.left) { printBSTInorder(node.left); } System.out.print(node.data + " "); if (null != node.right) { printBSTInorder(node.right); } } } class Node { Integer data; Node left; Node right; public Node(Integer data) { this.data = data; this.left = null; this.right = null; } }
Run Here http://ideone.com/rUQbn
Time Complexity O(N^2) N is number of nodes in BST
Space Complexity O(1) Ping me if anything wrong here
1 comment :
this can be done in O(n) time by doing inorder traversal in different way
traverse (right root left) instead (left root right)
Post a Comment