Given an element x, task is to find the value of its immediate smaller element.
Example :
Input : x = 30 (for above tree) Output : Immediate smaller element is 25
Explanation : Elements 2, 15, 20 and 25 are smaller than x i.e, 30, but 25 is the immediate smaller element and hence the answer.
Approach :
- Let res be the resultant node.
- Initialize the resultant Node as NULL.
- For every Node, check if data of root is greater than res, but less than x. if yes, update res.
- Recursively do the same for all nodes of the given Generic Tree.
- Return res, and res->key would be the immediate smaller element.
Below is the implementation of above approach :
C++
// C++ program to find immediate Smaller// Element of a given element in a n-ary tree.#include <bits/stdc++.h>using namespace std;// class of a node of an n-ary treeclass Node {public: int key; vector<Node*> child; // constructor Node(int data) { key = data; }};// Function to find immediate Smaller Element// of a given number xvoid immediateSmallerElementUtil(Node* root, int x, Node** res){ if (root == NULL) return; // if root is greater than res, but less // than x, then update res if (root->key < x) if (!(*res) || (*res)->key < root->key) *res = root; // Updating res // Number of children of root int numChildren = root->child.size(); // Recursive calling for every child for (int i = 0; i < numChildren; i++) immediateSmallerElementUtil(root->child[i], x, res); return;}// Function to return immediate Smaller// Element of x in treeNode* immediateSmallerElement(Node* root, int x){ // resultant node Node* res = NULL; // calling helper function and using // pass by reference immediateSmallerElementUtil(root, x, &res); return res;}// Driver programint main(){ // Creating a generic tree Node* root = new Node(20); (root->child).push_back(new Node(2)); (root->child).push_back(new Node(34)); (root->child).push_back(new Node(50)); (root->child).push_back(new Node(60)); (root->child).push_back(new Node(70)); (root->child[0]->child).push_back(new Node(15)); (root->child[0]->child).push_back(new Node(20)); (root->child[1]->child).push_back(new Node(30)); (root->child[2]->child).push_back(new Node(40)); (root->child[2]->child).push_back(new Node(100)); (root->child[2]->child).push_back(new Node(20)); (root->child[0]->child[1]->child).push_back(new Node(25)); (root->child[0]->child[1]->child).push_back(new Node(50)); int x = 30; cout << "Immediate smaller element of " << x << " is "; cout << immediateSmallerElement(root, x)->key << endl; return 0;} |
Python3
# Python code for the above approachclass Node: def __init__(self, key): self.key = key self.child = []# Function to find immediate Smaller Element of a given number xdef immediateSmallerElementUtil(root, x, res): if root is None: return # if root is greater than res, but less than x, then update res if root.key < x: if res[0] is None or res[0].key < root.key: res[0] = root # Recursive calling for every child for i in range(len(root.child)): immediateSmallerElementUtil(root.child[i], x, res) return# Function to return immediate Smaller Element of x in treedef immediateSmallerElement(root, x): # resultant node res = [None] immediateSmallerElementUtil(root, x, res) return res[0]if __name__ == "__main__": # Creating a generic tree root = Node(20) root.child.append(Node(2)) root.child.append(Node(34)) root.child.append(Node(50)) root.child.append(Node(60)) root.child.append(Node(70)) root.child[0].child.append(Node(15)) root.child[0].child.append(Node(20)) root.child[1].child.append(Node(30)) root.child[2].child.append(Node(40)) root.child[2].child.append(Node(100)) root.child[2].child.append(Node(20)) root.child[0].child[1].child.append(Node(25)) root.child[0].child[1].child.append(Node(50)) x = 30 print("Immediate smaller element of", x, "is", immediateSmallerElement(root, x).key) # This code is contributed by lokeshpotta20. |
Java
import java.util.*;// class of a node of an n-ary treeclass Node { int key; List<Node> child; // constructor Node(int data) { key = data; child = new ArrayList<>(); }}// Main classclass Main { // Function to find immediate smaller element // of a given number x static void immediateSmallerElementUtil(Node root, int x, Node[] res) { if (root == null) return; // if root is greater than res, but less // than x, then update res if (root.key < x) if (res[0] == null || res[0].key < root.key) res[0] = root; // Updating res // Number of children of root int numChildren = root.child.size(); // Recursive calling for every child for (int i = 0; i < numChildren; i++) immediateSmallerElementUtil(root.child.get(i), x, res); } // Function to return immediate smaller // element of x in tree static Node immediateSmallerElement(Node root, int x) { // resultant node Node[] res = new Node[1]; // calling helper function and using // pass by reference immediateSmallerElementUtil(root, x, res); return res[0]; } // Driver code public static void main(String[] args) { // Creating a generic tree Node root = new Node(20); root.child.add(new Node(2)); root.child.add(new Node(34)); root.child.add(new Node(50)); root.child.add(new Node(60)); root.child.add(new Node(70)); root.child.get(0).child.add(new Node(15)); root.child.get(0).child.add(new Node(20)); root.child.get(1).child.add(new Node(30)); root.child.get(2).child.add(new Node(40)); root.child.get(2).child.add(new Node(100)); root.child.get(2).child.add(new Node(20)); root.child.get(0).child.get(1).child.add(new Node(25)); root.child.get(0).child.get(1).child.add(new Node(50)); int x = 30; System.out.print("Immediate smaller element of " + x + " is "); System.out.println(immediateSmallerElement(root, x).key); }} |
C#
// C# program for the above approachusing System;using System.Collections.Generic;// class of a node of an n-ary treeclass Node { public int key; public List<Node> child; // constructor public Node(int data) { key = data; child = new List<Node>(); }}class GFG { // Function to find immediate smaller element // of a given number x static void immediateSmallerElementUtil(Node root, int x, Node[] res) { if (root == null) return; // if root is greater than res, but less // than x, then update res if (root.key < x) { if (res[0] == null || res[0].key < root.key) { res[0] = root; } } // Number of children of root int numChildren = root.child.Count; // Recursive calling for every child for (int i = 0; i < numChildren; i++) { immediateSmallerElementUtil(root.child[i], x, res); } } // Function to return immediate smaller // element of x in tree static Node immediateSmallerElement(Node root, int x) { Node[] res = new Node[1]; // calling helper function and using // pass by reference immediateSmallerElementUtil(root, x, res); return res[0]; } // Driver Code public static void Main() { Node root = new Node(20); root.child.Add(new Node(2)); root.child.Add(new Node(34)); root.child.Add(new Node(50)); root.child.Add(new Node(60)); root.child.Add(new Node(70)); root.child[0].child.Add(new Node(15)); root.child[0].child.Add(new Node(20)); root.child[1].child.Add(new Node(30)); root.child[2].child.Add(new Node(40)); root.child[2].child.Add(new Node(100)); root.child[2].child.Add(new Node(20)); root.child[0].child[1].child.Add(new Node(25)); root.child[0].child[1].child.Add(new Node(50)); int x = 30; Console.Write("Immediate smaller element of " + x + " is "); Console.WriteLine(immediateSmallerElement(root, x).key); }}// This code is contributed by codebraxnzt |
Javascript
class Node { constructor(key) { this.key = key; this.child = []; }}// Function to find immediate Smaller Element of a given number xfunction immediateSmallerElementUtil(root, x, res) { if (root == null) { return; } // if root is greater than res, but less than x, then update res if (root.key < x) { if (res[0] == null || res[0].key < root.key) { res[0] = root; } } // Recursive calling for every child for (let i = 0; i < root.child.length; i++) { immediateSmallerElementUtil(root.child[i], x, res); } return;}// Function to return immediate Smaller Element of x in treefunction immediateSmallerElement(root, x) { // resultant node let res = [null]; immediateSmallerElementUtil(root, x, res); return res[0];}// Creating a generic treelet root = new Node(20);root.child.push(new Node(2));root.child.push(new Node(34));root.child.push(new Node(50));root.child.push(new Node(60));root.child.push(new Node(70));root.child[0].child.push(new Node(15));root.child[0].child.push(new Node(20));root.child[1].child.push(new Node(30));root.child[2].child.push(new Node(40));root.child[2].child.push(new Node(100));root.child[2].child.push(new Node(20));root.child[0].child[1].child.push(new Node(25));root.child[0].child[1].child.push(new Node(50));let x = 30;console.log("Immediate smaller element of", x, "is", immediateSmallerElement(root, x).key); |
Output
Immediate smaller element of 30 is 25
Complexity Analysis:
- Time Complexity : O(N), where N is the number of nodes in N-ary Tree.
- Auxiliary Space : O(N), for recursive call(worst case when a node has N number of childs)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
