Beginner
1. Binary Search2. Linear Search3. Fibonacci Search4. Bubble Sort5. Insertion Sort6. Selection Sort7. Quick Sort8. Merge Sort9. Addition of two matrixes10. Subtraction of two matrixes11. Multiplication of two matrixes12. Transpose of given Matrix13. EUCLIDIAN GCD ALGORITHM14. Fabinocci Numbers with matrix multiplication15. Fast Exponential16. Modular inversion17. Prime seiving18. Heap(using array)19. Heapify20. Heap Sort21. Linear Probing22. Open Addressing23. Collision Avoidance24. Binary Search Tree Traversal Techniques25. Finding Kth Largest Element in Binary Tree26. Diameter of a Binary search tree27. Depth of Binary Tree28. Number of Nodes in BST29. Convert Array to Binary Tree30. Convert Array to General Tree31. Lowest Common AncestorFinding Kth Largest Element in Binary Tree
LEVEL:Beginner
Description
Given an array of integers. convert the array to a binary search tree and print the kth largest element in it
Input Format
First Line contains no of elements in the array Next line contains n elements representing the array elements Next line contains k
Output Format
Print the kth largest element in the binary search tree
5 3 2 1 4 5 2
4
8 1 2 3 4 5 6 7 8 5
4
10 10 50 4 8 0 6 2 4 8 555 3
10
Login to see Discussion
Approach
Step-i) Create a class Node with instances data of int type and left,right of Node type
Step-ii)create a default constructor which initializes left and right to null
Step-iii)create a constructor which accepts key as argument and assigns it to data
(this class is used to create a node of the tree)
Step-iv)create another class binary tree
Step-v)create a public method which return Node and takes root,node of Node type as arguments
Step-vi)if root is null assign node to root and return node
Step-vii)if data of root is less than data of node go to next step else go to ix
Step-viii)if right of root is null assign node to root right else call the insert method passing root.right and node as argument
Step-ix)if left of root is null assign node to root left else call the insert method passing root.left and node as argument
Step-x)return root
(now we are done with the insert method)
Step-xi)create another public method kth_largest which accepts root and k as argument
Step-xii)create variable curr of Node type assign root to it
Step-xiii)create another variable klargest of type Node and assign null to it
Step-xiv)initialize count to 0
Step-xv)if right of curr is null check if count is equal to k go to next step else go to xviii
Step-xvi) if equal to k assign curr to klargest
Step-xvii)increment count by one value and assing curr.left to curr
Step-xviii) create succ of type Node and assign curr.right to it
Step-xix)if succ.left not equal to null and succ.left != curr assign succ.left to succ
Step-xx)repeat step xix till succ.left not equal to null and succ.left not equal to curr
Step-xxi)if succ.left not equal to null assign curr to succ.left and curr.right to curr
Step-xxii)else assing null to succ.left
Step-xxiii)if count equal to k assign curr to klargest
Step-xxiv) assign curr.left to curr
Step-xxv)repeat steps xv to xxiv till curr is not equal to null
Step-xxvi)return klargest
Time Complexity: O(n)
Space Complexity: O(1)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution