BSTMAX - Editorial

editorial
1

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:

    1. Start from the root of the BST.
    1. Loop down to find the rightmost leaf of the BST.
    1. The rightmost leaf represents the maximum/largest node in the BST.
    1. 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.