Find Leftmost and Rightmost node of BST from its given preorder traversal

0 0 4 minutes read

Given a preorder sequence of the binary search tree of N nodes. The task is to find its leftmost and rightmost nodes.

Examples:

Input : N = 5, preorder[]={ 3, 2, 1, 5, 4 }
Output : Leftmost = 1, Rightmost = 5
The BST constructed from this 
preorder sequence would be:
         3
       /   \
      2     5
     /     /
    1     4
Leftmost Node of this tree is equal to 1
Rightmost Node of this tree is equal to 5

Input : N = 3 preorder[]={ 2, 1, 3}
Output : Leftmost = 1, Rightmost = 3

Naive Approach:
Construct BST from the given preorder sequence. See this post for understanding the code to construct bst from a given preorder. After constructing the BST, find the leftmost and rightmost node by traversing from root to leftmost node and traversing from root to rightmost node.
Time Complexity: O(N)
Space Complexity: O(N)

Efficient Approach:
Instead of constructing the tree, make use of the property of BST. The leftmost node in BST always has the smallest value and the rightmost node in BST always has the largest value.
So, from the given array we just need to find the minimum value for the leftmost node and the maximum value for the rightmost node.

Below is the implementation of the above approach:

C++

// C++ program to find leftmost and
// rightmost node from given preorder sequence
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the leftmost and 
// rightmost nodes of the BST whose 
// preorder traversal is given
void LeftRightNode(int preorder[], int n)
{
    // Variables for finding minimum 
    // and maximum values of the array
    int min = INT_MAX, max = INT_MIN;
 
    for (int i = 0; i < n; i++) {
         
        // Update the minimum
        if (min > preorder[i])
            min = preorder[i];
    
        // Update the maximum
        if (max < preorder[i])
            max = preorder[i];
    }
 
    // Print the values
    cout << "Leftmost node is " << min << "\n";
    cout << "Rightmost node is " << max;
}
 
// Driver Code
int main()
{
    int preorder[] = { 3, 2, 1, 5, 4 };
    int n = 5;
 
    LeftRightNode(preorder, n);
    return 0;
}

Java

// Java program to find leftmost and
// rightmost node from given preorder sequence
class GFG
{
 
// Function to return the leftmost and 
// rightmost nodes of the BST whose 
// preorder traversal is given
static void LeftRightNode(int preorder[], int n)
{
    // Variables for finding minimum 
    // and maximum values of the array
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
 
    for (int i = 0; i < n; i++)
    {
         
        // Update the minimum
        if (min > preorder[i])
            min = preorder[i];
     
        // Update the maximum
        if (max < preorder[i])
            max = preorder[i];
    }
    // Print the values
    System.out.println("Leftmost node is " + min);
    System.out.println("Rightmost node is " + max);
}
 
// Driver Code
public static void main(String[] args) 
{
        int preorder[] = { 3, 2, 1, 5, 4 };
        int n = 5;
        LeftRightNode(preorder, n);
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to find leftmost and
# rightmost node from given preorder sequence
 
# Function to return the leftmost and 
# rightmost nodes of the BST whose 
# preorder traversal is given
def LeftRightNode(preorder, n):
    # Variables for finding minimum 
    # and maximum values of the array
    min = 10**9
    max = -10**9
 
    for i in range(n):
         
        # Update the minimum
        if (min > preorder[i]):
            min = preorder[i]
     
        # Update the maximum
        if (max < preorder[i]):
            max = preorder[i]
 
    # Print the values
    print("Leftmost node is ",min)
    print("Rightmost node is ",max)
 
# Driver Code
 
preorder = [3, 2, 1, 5, 4]
n =len(preorder)
 
LeftRightNode(preorder, n)
 
# This code is contributed by mohit kumar 29

C#

// C# program to find leftmost and
// rightmost node from given preorder sequence
using System;
     
class GFG
{
 
// Function to return the leftmost and 
// rightmost nodes of the BST whose 
// preorder traversal is given
static void LeftRightNode(int []preorder, int n)
{
    // Variables for finding minimum 
    // and maximum values of the array
    int min = int.MaxValue, max = int.MinValue;
 
    for (int i = 0; i < n; i++)
    {
         
        // Update the minimum
        if (min > preorder[i])
            min = preorder[i];
     
        // Update the maximum
        if (max < preorder[i])
            max = preorder[i];
    }
    // Print the values
    Console.WriteLine("Leftmost node is " + min);
    Console.WriteLine("Rightmost node is " + max);
}
 
// Driver Code
public static void Main(String[] args) 
{
        int []preorder = { 3, 2, 1, 5, 4 };
        int n = 5;
        LeftRightNode(preorder, n);
 
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program to find leftmost and
// rightmost node from given preorder sequence
 
// Function to return the leftmost and 
// rightmost nodes of the BST whose 
// preorder traversal is given
function LeftRightNode(preorder, n)
{
    // Variables for finding minimum 
    // and maximum values of the array
    var min = 1000000000, max = -1000000000;
 
    for (var i = 0; i < n; i++) {
         
        // Update the minimum
        if (min > preorder[i])
            min = preorder[i];
    
        // Update the maximum
        if (max < preorder[i])
            max = preorder[i];
    }
 
    // Print the values
    document.write( "Leftmost node is " + min + "<br>");
    document.write( "Rightmost node is " + max);
}
 
// Driver Code
var preorder = [3, 2, 1, 5, 4];
var n = 5;
LeftRightNode(preorder, n);
 
</script>

Output:

Leftmost node is 1
Rightmost node is 5

Time Complexity: O(N)
Space Complexity: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!