using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        Node n = CreateTree();

        Node successor = new Node(char.Parse("f"));

        FindInOrderSuccessor(n, successor);

    }

    public static Node CreateTree(){

        Node a = new Node(char.Parse("a"));

        Node b = new Node(char.Parse("b"));

        Node c = new Node(char.Parse("c"));

        Node d = new Node(char.Parse("d"));

        Node e = new Node(char.Parse("e"));

        Node f = new Node(char.Parse("f"));

        Node g = new Node(char.Parse("g"));

        a.left = b;

        a.right = c;

        b.left = d;

        b.right = e;

        c.left = f;

        c.right = g;

        return a;

    }

    public static void FindInOrderSuccessor(Node root, Node lookingFor){

        Node successor = inOrder(root, new List<Node>(),lookingFor); 

​

        if(successor == null){

            Console.WriteLine("no successor");  

        }else{

            Console.WriteLine("Successor of " + lookingFor.val.ToString() + " is " + successor.val.ToString()); 

        }

        successor = inOrder(root, new Stack<Node>(),lookingFor); 

​

        if(successor == null){

            Console.WriteLine("no successor");  

        }else{

            Console.WriteLine("Successor of " + lookingFor.val.ToString() + " is " + successor.val.ToString()); 

        }

    }

    public static Node inOrder(Node n, List<Node> written, Node lookingFor){

        if(n.left != null){

            Node result = inOrder(n.left, written, lookingFor); 

            if(result != null) return result;

        }

        Console.WriteLine(n.val.ToString());

        if(written.Count > 0 &&  written[written.Count-1].val == lookingFor.val)

            return n;

        written.Add(n);

        if(n.right != null){

            Node result = inOrder(n.right, written, lookingFor);

            if(result != null)return result;

        }

        return null;

    }

    public static Node inOrder(Node n,Stack<Node> stack, Node lookingFor ){

        if(n.left != null){

            Node result = inOrder(n.left, stack, lookingFor);   

            if(result != null) return result;

        }

        Console.WriteLine(n.val.ToString());

        if(stack.Count>0 &&  stack.Peek().val == lookingFor.val)

            return n;

        stack.Push(n);

        if(n.right != null){

            Node result = inOrder(n.right, stack, lookingFor);

            if(result != null)return result;

        }

        return null;

    }

    public class Node{

        public char val;

        public Node left;

        public Node right;

        public Node(char x){

            val = x;    

        }

    }

}