using System.Collections;

using System.Collections.Generic;

using System.Diagnostics;

​

namespace BinaryTreeIterator {

    [DebuggerDisplay("{Value} L=#{Left} R=#{Right}")]

    public class Node {

        public Node(string value) {

            Value = value;

        }

​

        public Node Left { get; set; }

        public Node Right { get; set; }

        public string Value { get; }

    }

​

    public static class BinazryTreeSerializer {

        public static Node Deserialize(string source) {

            var q = new Queue<Node>();

            var i = 1;

            var root = new Node(source[0].ToString());

            q.Enqueue(root);

            while(i < source.Length) {

                var current = q.Dequeue();

                if(i < source.Length && source[i] != '\0') {

                    var node = new Node(source[i].ToString());

                    current.Left = node;

                    q.Enqueue(node);

                }

                i++;

                if(i < source.Length && source[i] != '\0') {

                    var node = new Node(source[i].ToString());

                    current.Right = node;

                    q.Enqueue(node);

                }

                i++;

            }

            return root;

        }

    }

​

    public class BinaryTreeSortedArray : IEnumerable<Node> {

        private readonly Node m_root;

​

        public BinaryTreeSortedArray(Node root) {

            m_root = root;

        }

​

        public IEnumerator<Node> GetEnumerator() {

            return new BinaryTreeIterator(m_root);

        }

​

        IEnumerator IEnumerable.GetEnumerator() {

            return GetEnumerator();

        }

​

        private class BinaryTreeIterator : IEnumerator<Node> {

            private readonly Node m_root;

            private readonly Stack<Node> parentsStack = new Stack<Node>();

​

            private void GoToBottomLeft(Node node) {

                if(node == null) {

                    return;

                }

                parentsStack.Push(node);

                GoToBottomLeft(node.Left);

            }

​

            public BinaryTreeIterator(Node root) {

                m_root = root;

                if(root.Left != null) {

                    GoToBottomLeft(root);

                }

                else {

                    Current = root;

                }

            }

            public void Dispose() {

            }

​

            public bool MoveNext() {

                if(Current == null) {

                    Current = parentsStack.Pop();

                    return true;

                }

                if(Current.Right == null) {

                    if(parentsStack.Count == 0) {

                        return false;

                    }

                }

                else {

                    GoToBottomLeft(Current.Right);

                }

                Current = parentsStack.Pop();

                return true;

            }

​

            public void Reset() {

                Current = m_root;

                parentsStack.Clear();

            }

​

            public Node Current { get; private set; }

            object IEnumerator.Current {

                get { return Current; }

            }

        }

    }

}

​