Hi, 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 ;).