Spread the post

Binary search find k'th largest element

In this post we are learning about how to find Binary tree or binary search tree kth largest element. Assume that following data are inserted on tree [450, 415, 462, 409, 419, 455, 496, 417, 526, 530].

Binary Tree or (BST) Binary Tree or Binary Search Tree 450415462496455526530419417409

View Tree

Find second largest element.

Second largest element 526 Find nth largest element of binary tree or binary search tree 450415462496455526530419417409

Find 6th largest element.

Second largest element 450 Find nth largest element of binary tree or binary search tree 450415462496455526530419417409

Find 8th largest element.

Second largest element 417 Find nth largest element of binary tree or binary search tree 450415462496455526530419417409

Algorithm:

Time complexity of this program O(n)

Execution process:

Code excecution process Code execution process to find kth largest element Stack Areamainroot(pointer)find_operationfind_Kth_small_value (int) =5result (int) =-1temp(pointer)find_Kth_large_elementkth_value (int) =5result(pointer)temp(pointer)find_Kth_large_elementkth_value (int) =5result(pointer)temp(pointer)find_Kth_large_elementkth_value (int) =5result(pointer)temp(pointer)find_Kth_large_elementkth_value (int) =5result(pointer)temp(pointer) Heap Areastruct Treedata (int)= 450left_child (pointer) right_child (pointer) struct Treedata (int)= 415left_child (pointer) right_child (pointer) struct Treedata (int)= 462left_child (pointer) right_child (pointer) struct Treedata (int)= 409left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 419left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 455left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 496left_child (pointer)= NULLright_child (pointer) struct Treedata (int)= 417left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 526left_child (pointer)= NULLright_child (pointer) struct Treedata (int)= 530left_child (pointer)= NULLright_child (pointer)= NULL

In this execution process not imagination all steps. below link click and view how to insert bst node, how to show all bst node and how to find kth largest element.

C program to print nth or kth largest binary tree or binary search tree node. Recursive approach.

Output
BST Data is :  409  415  417  419  450  455  462  496  526  530
 Invalid largest element [-1]

 [3] largest element is :  [496]

 [5] largest element is :  [455]

 [9] largest element is :  [415]

 Given largest element [11] not exist
 

Spread the post

Recommended Posts: