Prerequisites :- Binary Search Trees, BinaryTree traversal.
Problem :- Given a binary search tree, find the maximum/largest node in it.
Solution Approach :- The solution uses the property of a binary search tree where the rightmost node in the tree is the maximum/largest node. Therefore, to find the maximum value in the BST, you need to traverse down the right subtree until you reach the rightmost leaf.
Algorithm:
-
- Start from the root of the BST.
-
- Loop down to find the rightmost leaf of the BST.
-
- The rightmost leaf represents the maximum/largest node in the BST.
-
- Return the value of the rightmost leaf.
Time complexity :- O(h), where h is the height of the BST, if the tree is skewed, the complexity can go upto O(N).
Space complexity :- O(1), as no extra space is required.