public static bool IsSubTree(BinaryTreeNode<int> smallerTreeRoot, BinaryTreeNode<int> largerTreeRoot)
 {
     if (smallerTreeRoot == null) return true;
     else if (largerTreeRoot == null) return false;
     if (AreIdentical(smallerTreeRoot, largerTreeRoot)) return true;
     return IsSubTree(smallerTreeRoot, largerTreeRoot.Left) || IsSubTree(smallerTreeRoot, largerTreeRoot.Right);
 }

        private static BinaryTreeNode<int> BruteForce(BinaryTreeNode<int> root, int a, int b)
        {
            BinaryTreeNode<int> n1 = BinarySearchTree.Find(root, a);
            BinaryTreeNode<int> n2 = BinarySearchTree.Find(root, b);

            int d1 = ComputeLCA.Depth(n1);
            int d2 = ComputeLCA.Depth(n2);

            while (d1 > d2)
            {
                n1 = n1.Parent;
                d1--;
            }

            while (d2 > d1)
            {
                n2 = n2.Parent;
                d2--;
            }

            while (!object.Equals(n1, n2))
            {
                n1 = n1.Parent;
                n2 = n2.Parent;
            }

            return n1;
        }

 public static BinaryTreeNode<int> FindLowestCommonAncestorInBST(BinaryTreeNode<int> root, BinaryTreeNode<int> node1, BinaryTreeNode<int> node2)
 {
     if (root == null || node1 == null || node2 == null) return null;
     if (root.Value > Max(node1.Value, node2.Value)) return FindLowestCommonAncestorInBST(root.Left, node1, node2);
     if (root.Value < Min(node1.Value, node2.Value)) return FindLowestCommonAncestorInBST(root.Right, node1, node2);
     return root;
 }

        public void testNotInTree()
        {
            BinaryTreeNode<Int32> root = new BinaryTreeNode<Int32>(2);
            root.insert(5);
            root.insert(1);
            root.insert(16);
            bool exceptionCaught_v1 = false;
            bool exceptionCaught_v2 = false;
            bool exceptionCaught_v3 = false;

            #pragma warning disable 168
            try {
                Assert.AreEqual(eu.sig.training.ch03.binarytree.v1.BinaryTreeSearch.calculateDepth(root, 17), 0);
            } catch (TreeException e) {
                exceptionCaught_v1 = true;
            }
            try {
                Assert.AreEqual(eu.sig.training.ch03.binarytree.v2.BinaryTreeSearch
                    .calculateDepth(root, 17), 0);
            } catch (TreeException e) {
                exceptionCaught_v2 = true;
            }
            try {
                Assert.AreEqual(eu.sig.training.ch03.binarytree.v3.BinaryTreeSearch
                    .calculateDepth(root, 17), 0);
            } catch (TreeException e) {
                exceptionCaught_v3 = true;
            }
            Assert.IsTrue(exceptionCaught_v1);
            Assert.IsTrue(exceptionCaught_v2);
            Assert.IsTrue(exceptionCaught_v3);
            #pragma warning restore 168
        }

        public void ShouldCorrectlyCreateRootNode()
        {
            var root = new BinaryTreeNode<int>(null);

            Assert.AreEqual(null, root.Parent);
            Assert.IsTrue(root.IsRoot);
        }

        public static System.Collections.Generic.Dictionary<System.Int16, System.Collections.Generic.List<BinaryTreeNode>> getLevelLinkedList(BinaryTreeNode head)
        {
            System.Collections.Generic.Dictionary<System.Int16, System.Collections.Generic.List<BinaryTreeNode>> result
                = new System.Collections.Generic.Dictionary<System.Int16, System.Collections.Generic.List<BinaryTreeNode>>();
            short level = 0;
            System.Collections.Generic.List<BinaryTreeNode> list = new System.Collections.Generic.List<BinaryTreeNode>();
            list.Add(head);
            result.Add(level, list);

            while (true)
            {
                System.Collections.Generic.List<BinaryTreeNode> list_loop = result[level];
                list = new System.Collections.Generic.List<BinaryTreeNode>();
                result.Add(++level, list);
                foreach (BinaryTreeNode btn in list_loop)
                {
                    if (btn.LeftNode != null)
                    {
                        list.Add(btn.LeftNode);
                    }
                    if (btn.RightNode != null)
                    {
                        list.Add(btn.RightNode);
                    }
                }
                if (list.Count == 0)
                {
                    break;
                }
            }
            return result;
        }

        public static void findSumExDepth(BinaryTreeNode root, double threshold, int level = 0,
            System.Collections.Generic.List<BinaryTreeNode> list = null)
        {
            if (list == null)
            {
                list = new System.Collections.Generic.List<BinaryTreeNode>();
                list.Add(root);
                if (root.Data == threshold)
                {
                    printPath(list);
                }
            }
            else
            {
                list.Add(root);
                double tmp = threshold;
                for (int i = level; i >= 0; i--)
                {
                    tmp -= list[i].Data;
                    if (tmp == 0)
                    {
                        printPath(list, i);
                    }
                }
            }

            if (root.LeftNode != null)
            {
                findSumExDepth(root.LeftNode, threshold, level + 1, clone(list));
            }
            if (root.RightNode != null)
            {
                findSumExDepth(root.RightNode, threshold, level + 1, clone(list));
            }
        }

 public void NewNodeHasParent()
 {
     BinaryTreeNode<int> node = new BinaryTreeNode<int>(1);
     BinaryTreeNode<int> node2 = new BinaryTreeNode<int>(2);
     node.Left = node2;
     Assert.AreEqual(node2.Parent, node);
 }

 public void CanGetParent()
 {
     BinaryTreeNode<int> left = new BinaryTreeNode<int>(2);
     BinaryTreeNode<int> right = new BinaryTreeNode<int>(3);
     BinaryTreeNode<int> node = new BinaryTreeNode<int>(1, left, right);
     Assert.AreEqual(node.Left.Parent, node);
 }

        private BinaryTreeNode<Script> UnknowContact()
        {
            var root = new BinaryTreeNode<Script>(new Script
            {
                Question =
                    "Could you please tell me the name of the person who is responsible for the cleaning of your premises?",
                Actions = new Collection<ScriptAction>
                {
                    new UpdateContactName()
                },
            });

            root.Right = KnownContact();
            root.Left = new BinaryTreeNode<Script>(new Script
            {
                Question =
                    "We would like to send the relevant person some information on our services that they could find useful in the future. I do not " +
                    "need to speak to the person. Could you just tell me their name",
                Actions = new Collection<ScriptAction>
                {
                    new UpdateContactName()
                }
            });

            root.Left.Left = End(false);
            root.Left.Right = End(true);

            return root;
        }

        ////Algo
        //      5
        //   3     7
        // 1   4  6  8

        int VisitNode(BinaryTreeNode<int> treeNode)
        {
            int leftVal = 0, rightVal = 0;
            if(treeNode.Left == null)
            {
                leftVal = -1;
            }
            else
            {
                leftVal = VisitNode(treeNode.Left);
            }
            if(treeNode.Right == null)
            {
                rightVal = -1;
            }
            else
            {
                rightVal = VisitNode(treeNode.Right);
            }

            if(Math.Abs(leftVal - rightVal) > 1)
            {
                Console.WriteLine("Tree is not balanced");
            }

            return (leftVal > rightVal ? leftVal : rightVal) + 1;
        }

 public static BinaryTreeNode<int> FindNode(BinaryTreeNode<int> node, int searchValue)
 {
     if (node != null)
     {
         if (node.Value == searchValue)
         {
             CalcStack.Push(node.InitialValue.ToString());
             return node;
         }
         else
         {
             var right = FindNode(node.Right, searchValue);
             if (right != null)
             {
                 CalcStack.Push("*");
                 CalcStack.Push(node.InitialValue.ToString());
                 return right;
             }
             else
             {
                 var left = FindNode(node.Left, searchValue);
                 if (left != null)
                 {
                     CalcStack.Push("+");
                     CalcStack.Push(node.InitialValue.ToString());
                     return left;
                 }
             }
         }
     }
     return null;
 }

            public void Must_construct_root_node()
            {
                var systemUnderTest = new BinaryTreeNode();

                Assert.That(systemUnderTest.Ancestor, Is.Null);
                Assert.That(systemUnderTest.IsRoot, Is.True);
            }

 public static BinaryTreeNode inorderSucc(BinaryTreeNode orignal)
 {
     if (orignal.ParentNode == null && orignal.RightNode != null)
     {
         BinaryTreeNode btn = orignal.RightNode;
         while (btn != null)
         {
             if (btn.LeftNode != null)
             {
                 return btn.LeftNode;
             }
             btn = btn.RightNode;
         }
     }
     else
     {
         BinaryTreeNode btn = orignal;
         while (btn.ParentNode != null)
         {
             if (btn.ParentNode.LeftNode == btn)
             {
                 return btn.ParentNode;
             }
             btn = btn.ParentNode;
         }
         return btn;
     }
     return null;
 }

            public void Must_have_no_descendants()
            {
                var systemUnderTest = new BinaryTreeNode();

                Assert.That(systemUnderTest.LeftDescendant, Is.Null);
                Assert.That(systemUnderTest.RightDescendant, Is.Null);
            }

 public static void findSum(BinaryTreeNode root, double threshold, double count = 0,
     System.Collections.Generic.List<BinaryTreeNode> list = null)
 {
     if (list == null)
     {
         list = new System.Collections.Generic.List<BinaryTreeNode>();
     }
     double Data = root.Data;
     count += Data;
     list.Add(root);
     if (count == threshold)
     {
         printPath(list);
     }
     if (root.LeftNode != null)
     {
         findSum(root.LeftNode, threshold, count, clone(list));
         findSum(root.LeftNode, threshold);
     }
     if (root.RightNode != null)
     {
         findSum(root.RightNode, threshold, count, clone(list));
         findSum(root.RightNode, threshold);
     }
 }

        public void ShouldNotHaveChildNodesInitialy()
        {
            var root = new BinaryTreeNode<int>(null);

            Assert.IsFalse(root.HasLeftChild);
            Assert.IsFalse(root.HasRightChild);
        }

        public void SatisfiesBSTTest()
        {
            Func<BinaryTreeNode<int>, bool>[] functions = new Func<BinaryTreeNode<int>, bool>[]
            {
                SatisfiesBST.BruteForce,
                SatisfiesBST.Recursive,
                SatisfiesBST.InOrderTraversal,
                SatisfiesBST.Queue
            };

            for (int i = 0; i < 10; i++)
            {
                int[] data = ArrayUtilities.CreateRandomArray(10, 0, 20);

                BinaryTreeNode<int> root = new BinaryTreeNode<int>(data[0]);

                for(int j = 1; j < data.Length; j++)
                {
                    BinarySearchTree.Insert(root, data[j]);
                    Tests.TestFunctions(root, functions);
                }

                root = new BinaryTreeNode<int>(data[0]);

                for (int j = 1; j < data.Length; j++)
                {
                    BinaryTreeUtilities.AddRandomNode(root, data[j]);
                    Tests.TestFunctions(root, functions);
                }
            }
        }

 // tag::calculateDepth[]
 public static int CalculateDepth(BinaryTreeNode<int> t, int n)
 {
     int depth = 0;
     if (t.Value == n)
     {
         return depth;
     }
     else
     {
         if (n < t.Value)
         {
             BinaryTreeNode<int> left = t.Left;
             if (left == null)
             {
                 throw new TreeException("Value not found in tree!");
             }
             else
             {
                 return 1 + CalculateDepth(left, n);
             }
         }
         else
         {
             BinaryTreeNode<int> right = t.Right;
             if (right == null)
             {
                 throw new TreeException("Value not found in tree!");
             }
             else
             {
                 return 1 + CalculateDepth(right, n);
             }
         }
     }
 }

 // tag::calculateDepth[]
 public static int CalculateDepth(BinaryTreeNode<int> t, int n) {
     int depth = 0;
     if (t.Value == n) {
         return depth;
     } else {
         return TraverseByValue(t, n);
     }
 }