using System;

using System.Linq;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        BinaryTree tree = new BinaryTree();

        int[] source = {9,4,6,20,170,15,1}; 

        tree.root = tree.CreateBinaryTree(tree.root,source,0);

        tree.InOrder(tree.root);

        if(tree.HasPath(tree.root,15)){

            tree.routes.ForEach((item)=>{Console.Write(" {0} ",item);});

        }

    }

}

public class BinaryTree{

    public Tree root;

    public List<string> routes = new List<string>();

    public class Tree{

        public int val;

        public Tree right,left;

        public Tree(int val){

            this.val = val;

            this.right = null;

            this.left = null;

        }

    }

    public void InOrder(Tree root){

        if(root == null) return;

        InOrder(root.left);

        Console.Write(" {0} ",root.val);

        InOrder(root.right);

    } 

    public Tree CreateBinaryTree(Tree root,int[] source,int index){

        if(index < source.Length){

        Tree temp = new Tree(source[index]);

        root = temp;

        root.right = CreateBinaryTree(root.right,source,2*index+2);

        root.left = CreateBinaryTree(root.left,source,2*index+1);

            return root;

    }

    return root;

    }

    public bool HasPath(Tree root, int toFind,string rotation = null){

        if(root == null){ return false;}

        if(root.val != toFind){ routes.Add(rotation); return false;}

        if(!HasPath(root.right,toFind,"right")){

            //Console.Write(" {0} ",root.right.val);

            return false;

        }

        if(!HasPath(root.left,toFind,"left")){

            //Console.Write(" {0} ",root.left.val);

            return false;

        }

        return true;

    }

}