Given a binary tree replace all the node values with the sum of all its children values added to the current node value

       Input tree:                                Output tree:
recursiveSumTree

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;

namespace ConsoleApplication3
{
    public class Node
    {
        private Node left;
        private Node right;
        private int _value;
        public Node(Node left, Node right, int value)
        {
            this.left = left;
            this.right = right;
            this._value = value;
        }

        public Node getLeft()
        {
            return left;
        }

        public Node getRight()
        {
            return right;
        }

        public int value
        {
            get
            {
                return this._value;
            }
            set
            {
                this._value = value;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            //Initializing the tree structure
            Node bottomFirst = new Node(null, null, 4);
            Node bottomSecond = new Node(null, null, 5);
            Node bottomThird = new Node(null, null, 6);
            Node bottomFourth = new Node(null, null, 7);
            Node middleFirst = new Node(bottomFirst, bottomSecond, 2);
            Node middleSecond = new Node(bottomThird, bottomFourth, 3);
            Node root = new Node(middleFirst, middleSecond, 1);
            PreOrderTraversal(root);
            Console.WriteLine();
        }

        public static void PreOrderTraversal(Node root)
        {
            if (root == null)
            {
                return;
            }
            root.value = RecursiveSum(root);
            Console.Write(root.value + " ");
            PreOrderTraversal(root.getLeft());
            PreOrderTraversal(root.getRight());
        }

        public static int RecursiveSum(Node root)
        {
            if (root == null)
            {
                return 0;
            }
            else if (root.getLeft() != null && root.getRight() != null)
            {
                return root.value + RecursiveSum(root.getLeft()) + RecursiveSum(root.getRight());
            }
            else if (root.getLeft() != null)
            {
                return root.value + RecursiveSum(root.getLeft());
            }
            else if (root.getRight() != null)
            {
                return root.value + RecursiveSum(root.getRight());
            }
            return root.value;
        }
    }
}

Output
=======
28 11 4 5 16 6 7
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s