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 tree examples, t1, and t2, and your job is to find visible nodes that are not smaller than all parents. When you go down the t1 tree, you can find 4 such visible nodes. And for the second tree, 2 nodes are visible. The important thing is that the root node is always visible. The 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 an iterator that, by going deeper into the tree, carries a maximal value of parents so far. This way, I could 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.