private void expandAllParents(TreeNode node)
 {
     while (node.Parent != null) {
         node.Parent.Expanded = true;
         node = node.Parent;
     }
 }

        public async Task<TreeNode<NavigationNode>> GetTree()
        {
            // ultimately we will need to cache sitemap per site
            // we will implement a custom ICacheKeyResolver to resolve multi tenant cache keys

            if (rootNode == null)
            {
                log.LogDebug("rootnode was null so checking cache");
                string cacheKey = cacheKeyResolver.ResolveCacheKey(options.CacheKey);

                rootNode = (TreeNode<NavigationNode>)cache.Get(cacheKey);
               
                if(rootNode == null)
                {
                    log.LogDebug("rootnode was not in cache so building");
                    rootNode = await implementation.GetTree();
                    if (rootNode != null)
                    {
                        cache.Set(
                            cacheKey,
                            rootNode,
                            new MemoryCacheEntryOptions()
                            .SetSlidingExpiration(TimeSpan.FromSeconds(options.CacheDurationInSeconds)));
                    }
                }
                else
                {
                    log.LogDebug("rootnode was found in cache");
                }
                
            }

            return rootNode;
        }

    public void PopulateTreeView(string directoryValue, TreeNode parentNode )
    {
        string[] directoryArray =
           Directory.GetDirectories( directoryValue );

          try
          {
             if ( directoryArray.Length != 0 )
             {
                foreach ( string directory in directoryArray )
                {
                  substringDirectory = directory.Substring(
                  directory.LastIndexOf( '\\' ) + 1,
                  directory.Length - directory.LastIndexOf( '\\' ) - 1 );

                  TreeNode myNode = new TreeNode( substringDirectory );

                  parentNode.Nodes.Add( myNode );

                  PopulateTreeView( directory, myNode );
               }
             }
          } catch ( UnauthorizedAccessException ) {
            parentNode.Nodes.Add( "Access denied" );
          } // end catch
    }

        /// <summary>
        /// Build a Binary search tree for testing purpose
        /// </summary>
        /// <returns>The root node of the tree</returns>
        public static TreeNode<int> BuildBinarySearchTree()
        {
            TreeNode<int> root = new TreeNode<int>(15);
            TreeNode<int> l2l = new TreeNode<int>(13);
            TreeNode<int> l2r = new TreeNode<int>(20);
            root.Left = l2l;
            root.Right = l2r;

            TreeNode<int> l31 = new TreeNode<int>(11);
            TreeNode<int> l32 = new TreeNode<int>(14);
            TreeNode<int> l33 = new TreeNode<int>(17);

            l2l.Left = l31;
            l2l.Right = l32;
            l2r.Right = l33;

            TreeNode<int> l41 = new TreeNode<int>(9);
            TreeNode<int> l51 = new TreeNode<int>(6);
            TreeNode<int> l61 = new TreeNode<int>(5);
            TreeNode<int> l62 = new TreeNode<int>(7);

            l31.Left = l41;
            l41.Left = l51;
            l51.Left = l61;
            l51.Right = l62;

            return root;
        }

 public static void PrintTreeByInOrder(TreeNode<int> root)
 {
     if (root == null) return;
     PrintTreeByInOrder(root.Left);
     Console.Write("{0} ", root.Value);
     PrintTreeByInOrder(root.Right);
 }

 private void BuildTree()
 {
     foreach(Node idx in Data)
     {
         if(idx.Name == "Controllers")
         {
             TreeNode node = new TreeNode();
             node.ID = "idController";
             node.Text = LanguageRecords.Language.Instance["Controllers", null, "Controllers"];
             root.Controls.Add(node);
             BuildChildren(idx, node);
         }
         else if(idx.Name == "Modules")
         {
             TreeNode node = new TreeNode();
             node.ID = "idModules";
             node.Text = LanguageRecords.Language.Instance["Modules", null, "Modules"];
             root.Controls.Add(node);
             BuildChildren(idx, node);
         }
         else if(idx.Name == "Types")
         {
             TreeNode node = new TreeNode();
             node.ID = "idTypes";
             node.Text = LanguageRecords.Language.Instance["Types", null, "Types"];
             root.Controls.Add(node);
             BuildChildren(idx, node);
         }
     }
 }

        public async Task<TreeNode<NavigationNode>> GetTree()
        {
            // ultimately we will need to cache sitemap per site

            if (rootNode == null)
            {
                NavigationTreeXmlConverter converter = new NavigationTreeXmlConverter();

                await cache.ConnectAsync();
                byte[] bytes = await cache.GetAsync(cacheKey);
                if (bytes != null)
                {
                    string xml = Encoding.UTF8.GetString(bytes);
                    XDocument doc = XDocument.Parse(xml);
                    
                    rootNode = converter.FromXml(doc);
                }
                else
                {
                    rootNode = await BuildTree();
                    string xml2 = converter.ToXmlString(rootNode);

                    await cache.SetAsync(
                                        cacheKey,
                                        Encoding.UTF8.GetBytes(xml2),
                                        new DistributedCacheEntryOptions().SetSlidingExpiration(
                                            TimeSpan.FromSeconds(100))
                                            );
                                        }

                
            }

            return rootNode;
        }

    private void BindTree()
    {
        try
        {
            string TypeFlag = Request["TypeFlag"].ToString();
            if (!string.IsNullOrEmpty(TypeFlag))
            {
                DataTable dt = ApprovalFlowSetBus.GetBillTypeByType(TypeFlag);
                if (dt != null && dt.Rows.Count > 0)
                {
                    TreeNode node = new TreeNode();
                    node.Value = dt.Rows[0]["TypeFlag"].ToString();
                    node.Text = dt.Rows[0]["ModuleName"].ToString();
                    node.NavigateUrl = string.Format("javascript:javascript:void(0)");
                    BindTreeChildNodes(node);
                    Tree_BillTpye.Nodes.Add(node);
                    node.Expanded = true;
                }

                Tree_BillTpye.DataBind();
                Tree_BillTpye.Nodes[0].Selected = true;
            }
        }
        catch (Exception)
        {
            
            throw;
        }
     
    
    }

        static TreeNode<int> ConvertBST2DLL(TreeNode<int> root, out TreeNode<int> tail)
        {
            // No null root will be passed in. So no need to check

            // Handle head.
            TreeNode<int> head;

            if (root.Left == null)
            {
                head = root;
            }
            else
            {
                head = ConvertBST2DLL(root.Left, out tail);
                tail.Right = root;
                root.Left = tail;
            }

            // Handle tail.
            if (root.Right == null)
            {
                tail = root;
            }
            else
            {
                root.Right = ConvertBST2DLL(root.Right, out tail);
                root.Right.Left = root;
            }

            // clean up tail end
            tail.Right = null;

            return head;
        }

 public Tree(Coord root)
 {
     this.rootNode = new TreeNode();
     this.rootNode.SetRoot(root,new List<Coord>());
     this.nodes = new List<TreeNode>();
     this.nodes.Add(rootNode);
 }

 private void Process(TreeNode root, List<Tuple<PropertyInfo, List<String>>> input)
 {
     List<List<String>> output = new List<List<string>>();
     ISet<String> children = new HashSet<String>();
     foreach(var item in input)
     {
         children.Add(item.Item2[item.Item2.Count - 1]);
     }
     foreach(var child in children)
     {
         List<Tuple<PropertyInfo, List<String>>> owners = input.Where(item => item.Item2[item.Item2.Count - 1] == child).ToList();
         List<Tuple<PropertyInfo, List<String>>> removeds = new List<Tuple<PropertyInfo, List<string>>>();
         PropertyInfo childProp = null;
         foreach(var owner in owners)
         {
             var removed = new List<string>(owner.Item2);
             removed.RemoveAt(removed.Count - 1);
             if (removed.Count > 0)
                 removeds.Add(Tuple.Create(owner.Item1, removed));
             else
                 childProp = owner.Item1;
         }
         TreeNode childNode = new TreeNode(child);
         childNode.Parent = root;
         childNode.Property = childProp;
         root.Children.Add(childNode);
         Process(childNode, removeds);
     }
 }

    protected void Page_Load(object sender, EventArgs e)
    {
		if (!Page.IsPostBack)
		{
			DataSet ds = GetProductsAndCategories();

			// Loop through the category records.
			foreach (DataRow row in ds.Tables["Categories"].Rows)
			{
				// Use the constructor that requires just text
				// and a non-displayed value.
				TreeNode nodeCategory = new TreeNode(
					row["CategoryName"].ToString(),
					row["CategoryID"].ToString());

				TreeView1.Nodes.Add(nodeCategory);

				// Get the children (products) for this parent (category).
				DataRow[] childRows = row.GetChildRows(ds.Relations[0]);

				// Loop through all the products in this category.
				foreach (DataRow childRow in childRows)
				{
					TreeNode nodeProduct = new TreeNode(
						childRow["ProductName"].ToString(),
						childRow["ProductID"].ToString());
					nodeCategory.ChildNodes.Add(nodeProduct);
				}

				// Keep all categories collapsed (initially).
				nodeCategory.Collapse();
			}
		}
    }

 private void recursiceRemoveSelectedItemImage(TreeNode node)
 {
     foreach (TreeNode subnode in node.ChildNodes) {
         subnode.ImageUrl = string.Empty;
         recursiceRemoveSelectedItemImage(subnode);
     }
 }

        static void InOrderTraverseLoop(TreeNode<int> root)
        {
            Stack<TreeNode<int>> stack = new Stack<TreeNode<int>>();

            TreeNode<int> cur = root;

            while (cur != null)
            {
                if (cur.Visited == false && cur.Left != null)
                {
                    stack.Push(cur);
                    cur = cur.Left;
                    continue;
                }

                Console.Write(cur.Value);
                Console.Write(" ");

                if (cur.Right != null)
                {
                    cur = cur.Right;
                    continue;
                }

                if (!stack.IsEmpty())
                {
                    cur = stack.Pop();
                    cur.Visited = true;
                }
                else
                    cur = null;
            }
        }

    private TreeNode BuildTree()
    {
        this.root = new TreeNode((char)0);
        this.maxTreeDepth = 0;

        for (int stringIndex = 0; stringIndex < this.searchStrings.Length; ++stringIndex)
        {
            string s = this.searchStrings[stringIndex];
            this.maxTreeDepth = Math.Max(this.maxTreeDepth, s.Length);

            var node = this.root;
            for (int charIndex = 0; charIndex < s.Length; ++charIndex)
            {
                char c = s[charIndex];
                TreeNode newNode = node.GetTransition(c);
                if (newNode == null)
                {
                    int terminal = (charIndex == s.Length - 1) ? stringIndex : -1;
                    newNode = node.AddTransition(c, terminal);
                }
                else if (charIndex == s.Length - 1)
                {
                    newNode.Terminal = stringIndex;
                }

                node = newNode;
            }
        }

        ++this.maxTreeDepth;
        return this.root;
    }

    public int MinDepth(TreeNode root)
    {
        int depth = 0;
        Queue<TreeNode> nodes = new Queue<TreeNode>();

        if(root != null)
        {
            nodes.Enqueue(root);
        }

        while(nodes.Count != 0)
        {
            depth++;
            int noNodesInLevel = nodes.Count;
            for(int i = 0; i < noNodesInLevel; i++)
            {
                TreeNode node = nodes.Dequeue();
                if(node.left == null && node.right == null)
                {
                    return depth;
                }
                if(node.left != null)
                {
                    nodes.Enqueue(node.left);
                }
                if(node.right != null)
                {
                    nodes.Enqueue(node.right);
                }
            }
        }

        return depth;
    }

        public TreeNode rSortedListToBST(ListNode head, int size, out ListNode tail)
        {
            if (size == 1)
            {
                tail = head.next;
                return new TreeNode(head.val);
            }
            else
            {
                int left = size / 2;
                int right = size - 1 - left;

                var ltree = rSortedListToBST(head, left, out tail);

                var root = new TreeNode(tail.val);
                root.left = ltree;

                if (right > 0) {
                    var rtree = rSortedListToBST (tail.next, right, out tail);
                    root.right = rtree;
                } else {
                    tail = tail.next;
                }

                return root;
            }
        }

		public void FindNode_NodeThere_ReturnsTheNode()
		{
			var node = new TreeNode("AnotherNode");
			service.PushNode(node);
			service.PopNode();
			Assert.AreEqual(node, service.FindNode("AnotherNode"));
		}

 public static void GetPathWithGivenSum(TreeNode<int> startupNode, int sum)
 {
     var pathsWithGivenSum = new List<List<int>>();
     var currentPath = new LinkedList<int>();
     ConnectPathsWithGivenSum (startupNode, currentPath, pathsWithGivenSum, sum);
     PrintPathsWithGivenSum(pathsWithGivenSum,sum);
 }

   public override int GetHeight(TreeNode tn)
   {
      if (this.Layout == null)
         return 0;

      return this.Layout.ItemHeight - 4;
   }