using System;
using System.Diagnostics;

namespace SampleNamespace
{
  public class Node
    {
      public Node parent, left, right;
      public int key;
      public int accum;
    }
  
    public class SampleClass
    {
      static Node treeMinimum(Node x)
      {
        while (x.left != null)
          x = x.left;
        return x;
      }
      
        static Node treeSuccessor(Node x)
        {
          if (x.right != null)
            return treeMinimum(x.right);
          
          Node y = x.parent;
          while ((y != null) && (x == y.right))
          {
            x = y;
            y = y.parent;
          }
          return y;          
        }
      
        static Node accumDelete(ref Node tree, Node z)
          {
            Node y = (z.left == null || z.right == null) ? z : treeSuccessor(z);
            Node x = (y.left != null) ? y.left : y.right;
            
            if (x != null)
              x.parent = y.parent;
            
            if (y.parent == null)
              tree = x;
            else if (y == y.parent.left)
              y.parent.left = x;
            else
              y.parent.right = x;
            
              if (y != z)
                z.key = y.key;
              
              return y;
          }
      
         static bool accumVerify(Node x, int lb, int ub, int c)
         {
           int k = x.key + c;
           return x == null || (k > lb && k < ub &&
                                accumVerify(x.left, lb, k, c + x.accum) &&
                                accumVerify(x.right, k, ub, c + x.accum));
         }
      
        public static void Main()
        {
          Node
            root = new Node { key = 5, accum = 100 },
              a = new Node { parent = root, key = 6, accum = 300 },
                b = new Node { parent = root, key = 7, accum = 400 },
                  c = new Node { parent = a, key = 10, accum = 50000 };
          root.left = a;
          root.right = b;
          a.left = c;
          
          Console.WriteLine("Verify: {0}", accumVerify(root, int.MinValue, int.MaxValue, 0));
          
          
        } // End of Main function (program statup)
    } // End of SampleClass
} // End of SampleNamespace