Immediate Smaller element in an N-ary Tree

0 0 5 minutes read

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 tree
class Node {
 
public:
    int key;
    vector<Node*> child;
 
    // constructor
    Node(int data)
    {
        key = data;
    }
};
 
// Function to find immediate Smaller Element
// of a given number x
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) || (*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 tree
Node* 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 program
int 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 approach
class Node:
    def __init__(self, key):
        self.key = key
        self.child = []
 
# Function to find immediate Smaller Element of a given number x
def 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 tree
def 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 tree
class Node {
    int key;
    List<Node> child;
 
    // constructor
    Node(int data) {
        key = data;
        child = new ArrayList<>();
    }
}
 
// Main class
class 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 approach
 
using System;
using System.Collections.Generic;
 
 
// class of a node of an n-ary tree
class 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 x
function 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 tree
function immediateSmallerElement(root, x) {
    // resultant node
    let res = [null];
    immediateSmallerElementUtil(root, x, res);
    return res[0];
}
 
// Creating a generic tree
let 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)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!