Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Binary search tree (BST)
1.2.
Problem statement
2.
Approach
3.
Code in C++
3.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
How do you calculate a binary tree's maximum level sum?
4.2.
What is used to add elements to a binary tree?
4.3.
In a binary tree, how do you count the number of nodes?
4.4.
In a binary search tree, how do you add and remove elements?
5.
Conclusion
Last Updated: Mar 27, 2024

Sum and the Product of Minimum and Maximum Elements of a Binary Search Tree

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Binary Trees are popular Data Structures and have a wide range of applications throughout various fields. Binary Trees are also important when it comes to interviews with top tech companies. A mastery of Binary Trees could help us solve a lot of problems. In this article, we are going to take a look at one such problem.

Binary search tree (BST)

Before jumping to the question, let’s understand what a Binary search tree is:

A Binary search tree (BST)  is a type of binary tree in which the nodes are arranged in a specific order. It is also known as an ordered binary tree.

Properties of a Binary search tree (BST):

  • The value of all the nodes in the left subtree of a node is smaller than the node’s value.
  • All the nodes in the right subtree of a node are greater than the node’s value.
  • All the root node’s left and right subtrees must follow the above properties.

 

Example:

 

Binary Tree

 

Problem statement

We are given a Binary search tree. Our task is to find the sum and the product of the maximum and minimum elements of the binary search tree.

 

Example:

Input1: 

Binary Tree

 

Output1:  Sum = 30   

                Product = 189

 

Explanation: 

The maximum element = 21, and the minimum element = 9,

Sum = 21 + 9 = 30

Product = 21 * 9 = 189

 

Input2:

 

Binary Tree

 

Output2: Sum = 88

               Product = 1207

 

Explanation: 

The maximum element = 71 and the minimum element = 17,

Sum = 71 + 17 = 88

Product = 71 * 17 = 1207

Approach

The idea is simple, find the minimum and the maximum value in the binary search tree. After that, find the required sum and the product of the minimum and maximum elements.

In a Binary search tree (BST), the left child of each node must be less than its parent, and the right child must be greater than its parent node. 

Because of its ordered structure, finding the maximum and the minimum value in the Binary search tree is a simple operation.

So, if we consider the root node of the Binary search tree (BST), the left subtree of the binary search tree must have nodes with values less than or equal to the root node, and the right subtree must have nodes with values greater than the root node.

So, the node with minimum and maximum value in the binary search tree is the tree’s leftmost and rightmost node, respectively.
 

Steps for finding the minimum element in the Binary search tree:

  • Declare a curr pointer pointing to the root of the Binary search tree.
  • Run a while loop till curr -> left != NULL  and do curr = curr -> left inside the while loop.
  • After the completion of the loop, return curr->data,  which is the minimum value in the Binary search tree.
     

Steps for finding the maximum element in the Binary search tree:

  • Declare a curr pointer pointing to the root of the Binary search tree.
  • Run a while loop till curr -> right != NULL  and do curr = curr -> right inside the while loop.
  • After the completion of the loop, return curr->data,  which is the maximum value in the Binary search tree.
     

Finally, print the sum and the product of minimum and maximum values of the Binary search tree.

Let’s understand the above approach with an example:

 

Input: 

 

Binary Tree

 

Steps for finding the minimum element:

 

Initially, the curr pointer points to the root of the Binary search tree.

 

Binary Tree

 

Now, curr->left != NULL, so we move the curr pointer to the left node, curr = curr -> left.

 

Binary Tree

 

curr->left != NULL, so we move the curr pointer to the left node, curr = curr -> left.

 

Binary Tree

 

Similarly, curr = curr -> left.

 

Binary Tree

 

Now, curr -> left = NULL, return the curr -> data, which is the minimum element in the binary search tree.

 

Steps for finding maximum element:

 

Initially, the curr pointer points to the root of the Binary search tree.

 

Binary Tree

 

Now, curr->right != NULL, so we move the curr pointer to the right node, curr = curr -> right.

 

Binary Tree

 

Similarly, curr = curr -> right.

 

Binary Tree

 

Here curr -> right = NULL, return the curr -> data, which is the maximum element in the Binary search tree.

Finally, print the sum and the product of minimum and maximum elements of the Binary search tree.

Check out this problem - Diameter Of Binary Tree

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Code in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

Node* new_node(int x)
{
    Node* freshnode = new Node();
    freshnode->data = x;
    freshnode->left = NULL;
    freshnode->right = NULL;

    return (freshnode);
}
Node* insert_bst( Node* node, int data)
{

    if (node == NULL)
        return (new_node(data));
    else {
        if (data <= node->data)
            node->left = insert_bst(node->left, data);
        else
            node->right = insert_bst(node->right, data);

        return node;
    }
}

int min_val( Node* root)
{
    Node* curr = root;

    while (curr->left != NULL)
        curr = curr->left;

    return curr->data;
}

int max_val(Node* root)
{
    Node* curr = root;

    while (curr->right != NULL)
        curr = curr->right;

    return curr->data;
}

int main()
{
    Node* root = NULL;
    root = insert_bst(root, 15);
    insert_bst(root, 11);
    insert_bst(root, 18);
    insert_bst(root, 10);
    insert_bst(root, 13);
    insert_bst(root, 16);
    insert_bst(root, 21);
    insert_bst(root, 9);
    insert_bst(root, 12);

    int minm = min_val(root);
    int maxm = max_val(root);

    cout << "Sum = " << minm + maxm << endl;
    cout << "Product = " << minm*maxm << endl;


    return 0;
}

 

Output

Sum = 30
Product = 189

Complexity Analysis

Time complexity: O(n), where n is the number of nodes in the given tree as in the worst case, we have to traverse every node of the tree.

Space complexity: O(1) requires constant extra space.

You can also read about insertion into bst.

Frequently Asked Questions

How do you calculate a binary tree's maximum level sum?

The idea is to traverse the tree in level order. Process nodes of different levels separately while traversing. Calculate the sum of nodes in each level being processed and keep track of the highest sum.

What is used to add elements to a binary tree?

The Insert function adds a new element to the appropriate location in a binary search tree. The Insert function must be designed to not violate the binary search tree's property at each value. Allocate memory for the tree.

In a binary tree, how do you count the number of nodes?

Return the value of (2^height – 1) as the resultant count of nodes if the left and right heights of the given Tree are equal to the current root value. Otherwise, call the function for the left and right subtrees recursively and return the sum + 1 as the resultant node count.

In a binary search tree, how do you add and remove elements?

Step1: Compare the value inserted with the current node value at the Tree's root node. 

Step2: Go to the left subtree if the value to be inserted is less than or equal to the root node value; otherwise, go to the right subtree.

Step3: Compare the value to the value of the subtree's root node, and then repeat step 2.

 

Conclusion

This article discussed the binary search tree, its properties, and how to find the sum and the product of minimum and maximum elements of the binary search tree with examples for a better understanding and its complete C++ code.

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!

Recommended Problems:

Thank you for reading!

Previous article
Node with the Maximum Value in a Binary Search Tree
Next article
Find if a given Array can Represent Preorder Traversal of BST
Live masterclass