using System;

using System.Collections.Generic;

​

// Create a N-ary tree and find a given element K in it

public class Node

{

    public int Key;

    public string Value;

    public List<Node> Children;

    public void Insert(int key, string val)

    {

        if(this.Children==null)

            this.Children= new List<Node>();

​

        this.Children.Add(new Node(){Key = key, Value = val});

    }

}

​

public class NaryTree

{

    private Node root;

    public NaryTree(Node root)

    {

        this.root = root;

    }

​

    public Node Search(int key)

    {   Node found = null;

        Stack<Node> stack = new Stack<Node>();

        stack.Push(this.root);

        while(stack.Count!=0)

        {

            var current = stack.Pop();

            if(current.Key == key)

            {

                found=current;

                break;

            }

            else

            {

                if( current.Children!=null)

                {

                    foreach(var node in current.Children)

                    {

                        stack.Push(node);

                    }

                }

            }

        }

     return found;

    }

}

​

public class Driver

{

    public static void Main()

    {

        NaryTree tree = new NaryTree(

            new Node

            {

                Key=5,

                Value = "Five", 

                Children = new List<Node>()

                {

                    new Node

                    {

                        Key = 1, 

                        Value = "One",

                        Children = new List<Node>()

                        {

                            new Node{Key=2},

                            new Node{Key=3}

                        }

                    }                   

                    , new Node

                    {

                        Key = 4, 

                        Children = new List<Node>()

                        {                           

                            new Node{ Key=6, Value = "Six" }, new Node{Key=7, Value="Seven"}, new Node{Key=8, Value="Eight"},

                            new Node{ Key=9, Children = new List<Node>() {new Node{Key=10}, new Node{Key=11} }}

                        }

                    }                   

                    , new Node

                    {

                        Key = 12, Value="Twelve",

                        Children = new List<Node>() { new Node{Key=13, Value = "Thirteen"}, new Node{Key=14, Value = "Fourteen"}}

                    }

                }

            }

        );

        var node = tree.Search(7);

        Console.WriteLine(node==null ? "Not Found" : node.Value);

        node=tree.Search(12);

        Console.WriteLine(node==null ? "Not Found" : node.Value);

        node=tree.Search(21);

        Console.WriteLine(node==null ? "Not Found" : node.Value);

    }

}