Next Larger element in n-ary tree

// C# program to find next larger element
// in an n-ary tree.
using System;
using System.Collections.Generic;

class GFG
{

// Structure of a node of an n-ary tree
class Node
{
    public int key;
    public List<Node> child;
};
static Node res;

// Utility function to create a new tree node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.child = new List<Node>();
    return temp;
}

static void nextLargerElementUtil(Node root, 
                                  int x)
{
    if (root == null)
        return;

    // if root is less than res but 
    // greater than x, update res
    if (root.key > x) 
        if ((res == null || 
            (res).key > root.key))
            res = root; 

    // Number of children of root
    int numChildren = root.child.Count;

    // Recur calling for every child
    for (int i = 0; i < numChildren; i++)
        nextLargerElementUtil(root.child[i], x);

    return;
}

// Function to find next Greater element 
// of x in tree
static Node nextLargerElement(Node root,    
                                  int x)
{
    // resultant node
    res = null;

    // calling helper function
    nextLargerElementUtil(root, x);

    return res;
}

// Driver Code
public static void Main(String[] args)
{
    /* Let us create below tree
    *             5
    *         / | \
    *         1 2 3
    *     / / \ \
    *     15 4 5 6
    */
    Node root = newNode(5);
    (root.child).Add(newNode(1));
    (root.child).Add(newNode(2));
    (root.child).Add(newNode(3));
    (root.child[0].child).Add(newNode(15));
    (root.child[1].child).Add(newNode(4));
    (root.child[1].child).Add(newNode(5));
    (root.child[2].child).Add(newNode(6));

    int x = 5;

    Console.Write("Next larger element of " +
                                 x + " is ");
    Console.Write(nextLargerElement(root, x).key + "\n");
}
}

// This code is contributed by PrinciRaj1992

using System;
using System.Collections.Generic;

class Node {
    // Structure of a node of an n-ary tree
    public int val;
    public List<Node> children;

    public Node()
    {
        val = 0;
        children = new List<Node>();
    }
}

public class MainClass {
    // Utility function to create a new tree node
    static Node NewNode(int val)
    {
        Node temp = new Node();
        temp.val = val;
        temp.children = new List<Node>();
        return temp;
    }

    // Function to perform post-order traversal and store
    // nodes in a list
    static void PostOrder(Node root, List<int> nodes)
    {
        if (root == null)
            return;

        // Recursively perform post-order traversal for each
        // child node
        foreach(Node child in root.children)
        {
            PostOrder(child, nodes);
        }

        // Add the current node value to the list after
        // processing all its children
        nodes.Add(root.val);
    }

    // Function to find the next larger element for each
    // node in the tree
    static Dictionary<int, int> FindNextLarger(Node root)
    {
        List<int> nodes = new List<int>();
        Dictionary<int, int> nextLarger
            = new Dictionary<int, int>();
        PostOrder(root, nodes);

        Stack<int> stack = new Stack<int>();
        for (int i = nodes.Count - 1; i >= 0; i--) {
            // Keep popping elements from the end of the
            // list until we find the next larger element
            while (stack.Count > 0
                   && stack.Peek() <= nodes[i]) {
                stack.Pop();
            }

            // If a next larger element is found, store it
            // in the dictionary
            if (stack.Count > 0) {
                nextLarger[nodes[i]] = stack.Peek();
            }
            // If no next larger element is found, set the
            // value to -1
            else {
                nextLarger[nodes[i]] = -1;
            }

            stack.Push(nodes[i]);
        }

        return nextLarger;
    }

    public static void Main()
    {
        Node root = NewNode(8);
        root.children.Add(NewNode(3));
        root.children.Add(NewNode(10));
        root.children[0].children.Add(NewNode(1));
        root.children[0].children.Add(NewNode(6));
        root.children[0].children[1].children.Add(
            NewNode(4));
        root.children[0].children[1].children.Add(
            NewNode(7));
        root.children[1].children.Add(NewNode(14));

        int target = 4;
        Dictionary<int, int> nextLarger
            = FindNextLarger(root);
        int nextLargerValue;
        if (nextLarger.TryGetValue(target,
                                   out nextLargerValue)) {
            Console.WriteLine("The next larger element for "
                              + target
                              + " is: " + nextLargerValue);
        }
        else {
            Console.WriteLine("The next larger element for "
                              + target + " is: -1");
        }
    }
}