Binary Tree Visible Nodes Counting

imageHi, today I would like to share with you solution of the code puzzle with binary tree. There are 2 trees examples t1 and t2 and your job is to find visible nodes and visible nodes are that are not smaller then all parents. When you go down for t1 tree you can find 4 such visible nodes. And for the second tree there are 2 nodes that are visible. Important thing is that the root node is always visible. Tree is defined with 3 fields x is the node value, l is the left node and r is the right node. Below you can find my solution for looking for all visible nodes in binary trees in C#. I decided to use iterator that by going deeper into the tree carry maximal value of parents so far. In this way I was able to find visible nodes in O(N) complexity. All comments are welcome. I hope you like this puzzle solution.

namespace TreeVisibleNodes
{
    using System;
    using System.Collections.Generic;

    class Tree
    {
        public int x;
        public Tree l;
        public Tree r;
    }

    class TreeVisibleSolution
    {
        #region Tests
        static void Main(string[] args)
        {
            var t0 = default(Tree);

            var t1 = new Tree
            {
                x = 5,
                l = new Tree
                {
                    x = 3,
                    l = new Tree {x = 20},
                    r = new Tree {x = 21}
                },
                r = new Tree
                {
                    x = 10,
                    r = new Tree {x = 1}
                }
            };

            var t2 = new Tree
            {
                x = 8,
                l = new Tree
                {
                    x = 2,
                    l = new Tree {x = 8},
                    r = new Tree {x = 7}
                },
                r = new Tree {x = 3}
            };

            var testEngine = new Func<string, Tree, int, string>
            (
                (name, tree, expexted) =>
                {
                    var count = Solution(tree);
                    return string.Format("Solution({0}) equals {1,2} {2}",
                        name, count, count == expexted ? "PASS" : "FAIL");
                }
            );

            Console.WriteLine(testEngine("t0", t0, -1));
            Console.WriteLine(testEngine("t1", t1,  4));
            Console.WriteLine(testEngine("t2", t2,  2));
            Console.ReadKey(true);
        }
        #endregion Tests

        #region Solution
        private static int Solution(Tree T)
        {
            if (T == null)
            {
                return -1;
            }

            var count = 0;

            var stack = new Stack<Tuple<int, Tree>>();
            stack.Push(new Tuple<int, Tree>(T.x, T));
            
            while (stack.Count > 0)
            {
                var n = stack.Pop();
                if (n.Item1 <= n.Item2.x)
                {
                    ++count;
                }
                var max = Math.Max(n.Item1, n.Item2.x);
                if (n.Item2.l != null)
                {
                    stack.Push(new Tuple<int, Tree>(max, n.Item2.l));
                }
                if (n.Item2.r != null)
                {
                    stack.Push(new Tuple<int, Tree>(max, n.Item2.r));
                }
            }

            return count;
        }
        #endregion Solution
    }
}

P ;).

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.