Learn basic concept of c , c++ and python programming in regularcodes.com

Spread the post

Find binary search second largest element

The recursive approach to find second largest element of binary tree or binary search tree. supposed following data [89, 79, 150, 56, 654, 43, 78, 437, 600] are inserted on binary search tree.

Given BST

Try it Yourself

Given example to find second largest element.

Second largest BST node

Algorithm:

Case 1: When root left subtree and right subtree are exist. Then follow this approach.

In this algorithm visit all bst node using recursion. Initial both pointer ( *first and *second ) are pointed to root node. if node data value are greater. Then *second pointer= *first pointer and *first pointer=* current visited node. continue this process and find second largest element.

Case 2: Special when root left subtree or right subtree are not exist. then before proceed first case do some modification. Change first_big and second_big initial value to main() function.

Time complexity of this Algorithm O(n).

Execution process to find second largest element

This demo try to visualize how to find second largest element of given binary search tree.

Stack Areamainfirst_big (int) =89root(pointer)second_big (int) =89second_largestfirst(pointer)second(pointer)temp(pointer)second_largestfirst(pointer)second(pointer)temp(pointer)second_largestfirst(pointer)second(pointer)temp(pointer) Heap Areastruct Treedata (int)= 89left_child (pointer) right_child (pointer) struct Treedata (int)= 79left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 150left_child (pointer)= NULLright_child (pointer) struct Treedata (int)= 56left_child (pointer) right_child (pointer) struct Treedata (int)= 654left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 43left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 78left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 437left_child (pointer)= NULLright_child (pointer) struct Treedata (int)= 600left_child (pointer)= NULLright_child (pointer)= NULL

second Largest element of this given tree is [600]. Recursive approach.

Click To Visualize Code

Accepted Output

Given BST tree node is:

50, 70, 30, 90, 20, 10, 15, 60, 80

Result :

Second large element data is [80]

Given BST tree node is:

50, 70, 30, 90, 20, 50, 45, 320, 80

Result :

Second large element data is [90]

Below in C implementation of this problem

Output
43 56 78 79 89 150 437 600 654
 Second Big element is 600
 Free BST node
  

Spread the post