using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Start");

        var root = CreateNode(5);

        root.Left = CreateNode(3);

        root.Right = CreateNode(9);

        root.Left.Left = CreateNode(6);

        root.Left.Right = CreateNode(4);

        root.Left.Left.Right = CreateNode(7);

        int count = FindSum(root);

        Console.WriteLine("count: " + count);

        Console.WriteLine("End");

    }

    public class Node {

        public int Val;

        public Node Left;

        public Node Right;

    }

    public static Node CreateNode(int val) {

        Node temp = new Node();

        temp.Val = val;

        return temp;

    }

    public static int FindSum(Node root) {

        Queue<Node> queue = new Queue<Node>();

        queue.Enqueue(root);

        int count = 0;

        while (queue.Count>0)

        {

            int leaf = 0;

            int nonleaf = 0;

            int length = queue.Count;

            while (length > 0)

            {

                Node node = queue.Peek();

                queue.Dequeue();

                if (node.Left == null && node.Right == null)

                    leaf += node.Val;

                else

                    nonleaf += node.Val;

                if (node.Left != null)

                    queue.Enqueue(node.Left);

                if (node.Right != null)

                    queue.Enqueue(node.Right);

                length -= 1;

            }

                count += (leaf & nonleaf);

        }

            return count;

    }

}