<commit_before>﻿using System;
using System.Collections.Generic;
using DataStructuresAlgorithms.AbstractDataTypes;

namespace DataStructuresAlgorithms.DataStructures.Tree
{
    public class BinaryTree<T>
    {
        public Node<T> Root { get; private set; }

        public BinaryTree(Node<T> root)
        {
            Root = root;
        }

        public BinaryTree() : this(null) { }

        public int Height
        {
            get
            {
                return ComputeHeight(Root);
            }
        }

        public static int ComputeHeight(Node<T> node)
        {
            if (node == null)
            {
                return -1;
            }
            else
            {
                return 1 + Math.Max(ComputeHeight(node.Left),
                    ComputeHeight(node.Right));
            }
        }

        public static IEnumerable<Node<T>> PreOrderTraversalRecursiveIterator(Node<T> node)
        {
            if (node == null) yield break;

            yield return node;
            foreach (var val in PreOrderTraversalRecursiveIterator(node.Left))
                yield return val;
            foreach (var val in PreOrderTraversalRecursiveIterator(node.Right))
                yield return val;
        }

        public static IEnumerable<Node<T>> InOrderTraversalRecursiveIterator(Node<T> node)
        {
            if (node == null) yield break;

            foreach (var val in InOrderTraversalRecursiveIterator(node.Left))
                yield return val;
            yield return node;
            foreach (var val in InOrderTraversalRecursiveIterator(node.Right))
                yield return val;
        }

        public static IEnumerable<Node<T>> PostOrderTraversalRecursiveIterator(Node<T> node)
        {
            if (node == null) yield break;

            foreach (var val in PostOrderTraversalRecursiveIterator(node.Left))
                yield return val;
            foreach (var val in PostOrderTraversalRecursiveIterator(node.Right))
                yield return val;
            yield return node;
        }

        public static IEnumerable<Node<T>> PreOrderTraversalIterativeIterator(Node<T> node)
        {
            if (node == null) yield break;

            var stack = new StackSinglyLinkedList<Node<T>>();
            stack.Push(node);
            while (stack.Count > 0)
            {
                Node<T> curr = stack.Pop();
                yield return curr;
                foreach (var child in curr.EnumerateRL())
                {
                    stack.Push(child);
                }
            }
        }

        public static IEnumerable<Node<T>> InOrderTraversalIterativeIterator(Node<T> node)
        {
            var stack = new StackSinglyLinkedList<Node<T>>();
            Node<T> curr = node;
            while (stack.Count > 0 || curr != null)
            {
                if (curr != null)
                {
                    stack.Push(curr);
                    curr = curr.Left;
                }
                else
                {
                    curr = stack.Pop();
                    yield return curr;
                    curr = curr.Right;
                }
            }
        }

        public static IEnumerable<Node<T>> PostOrderTraversalIterativeIterator(Node<T> node)
        {
            var stack = new StackSinglyLinkedList<Node<T>>();
            Node<T> lastNodeVisited = null;
            var curr = node;
            Node<T> peekNode = null;
            while(stack.Count > 0 || curr != null)
            {
                if(curr != null)
                {
                    stack.Push(curr);
                    curr = curr.Left;
                }
                else
                {
                    peekNode = stack.FirstNode.Value;
                    if(peekNode.Right != null && peekNode.Right != lastNodeVisited)
                    {
                        curr = peekNode.Right;
                    }
                    else
                    {
                        lastNodeVisited = stack.Pop();
                        yield return lastNodeVisited;
                        curr = null;
                    }
                }
            }
        }

        public static IEnumerable<Node<T>> BreadthFirstTraversalQueue(Node<T> node)
        {
            if (node == null) yield break;

            yield return node;
            var queue = new QueueSinglyLinkedList<Node<T>>();<commit_msg>Using IStack<T> and IQueue<T> instead of implementations<commit_after>﻿using System;
using System.Collections.Generic;
using DataStructuresAlgorithms.AbstractDataTypes;

namespace DataStructuresAlgorithms.DataStructures.Tree
{
    public class BinaryTree<T>
    {
        public Node<T> Root { get; private set; }

        public BinaryTree(Node<T> root)
        {
            Root = root;
        }

        public BinaryTree() : this(null) { }

        private static IStack<Node<T>> GetStackImpl()
        {
            return new StackSinglyLinkedList<Node<T>>();
        }

        private static IQueue<Node<T>> GetQueueImpl()
        {
            return new QueueSinglyLinkedList<Node<T>>();
        }

        public int Height
        {
            get
            {
                return ComputeHeight(Root);
            }
        }

        public static int ComputeHeight(Node<T> node)
        {
            if (node == null)
            {
                return -1;
            }
            else
            {
                return 1 + Math.Max(ComputeHeight(node.Left),
                    ComputeHeight(node.Right));
            }
        }

        public static IEnumerable<Node<T>> PreOrderTraversalRecursiveIterator(Node<T> node)
        {
            if (node == null) yield break;

            yield return node;
            foreach (var val in PreOrderTraversalRecursiveIterator(node.Left))
                yield return val;
            foreach (var val in PreOrderTraversalRecursiveIterator(node.Right))
                yield return val;
        }

        public static IEnumerable<Node<T>> InOrderTraversalRecursiveIterator(Node<T> node)
        {
            if (node == null) yield break;

            foreach (var val in InOrderTraversalRecursiveIterator(node.Left))
                yield return val;
            yield return node;
            foreach (var val in InOrderTraversalRecursiveIterator(node.Right))
                yield return val;
        }

        public static IEnumerable<Node<T>> PostOrderTraversalRecursiveIterator(Node<T> node)
        {
            if (node == null) yield break;

            foreach (var val in PostOrderTraversalRecursiveIterator(node.Left))
                yield return val;
            foreach (var val in PostOrderTraversalRecursiveIterator(node.Right))
                yield return val;
            yield return node;
        }

        public static IEnumerable<Node<T>> PreOrderTraversalIterativeIterator(Node<T> node)
        {
            if (node == null) yield break;

            IStack<Node<T>> stack = GetStackImpl();
            stack.Push(node);
            while (stack.Count > 0)
            {
                Node<T> curr = stack.Pop();
                yield return curr;
                foreach (var child in curr.EnumerateRL())
                {
                    stack.Push(child);
                }
            }
        }

        public static IEnumerable<Node<T>> InOrderTraversalIterativeIterator(Node<T> node)
        {
            IStack<Node<T>> stack = GetStackImpl();
            Node<T> curr = node;
            while (stack.Count > 0 || curr != null)
            {
                if (curr != null)
                {
                    stack.Push(curr);
                    curr = curr.Left;
                }
                else
                {
                    curr = stack.Pop();
                    yield return curr;
                    curr = curr.Right;
                }
            }
        }

        public static IEnumerable<Node<T>> PostOrderTraversalIterativeIterator(Node<T> node)
        {
            IStack<Node<T>> stack = GetStackImpl();
            Node<T> lastNodeVisited = null;
            var curr = node;
            Node<T> peekNode = null;
            while(stack.Count > 0 || curr != null)
            {
                if(curr != null)
                {
                    stack.Push(curr);
                    curr = curr.Left;
                }
                else
                {
                    peekNode = stack.Peek();
                    if(peekNode.Right != null && peekNode.Right != lastNodeVisited)
                    {
                        curr = peekNode.Right;
                    }
                    else
                    {
                        lastNodeVisited = stack.Pop();
                        yield return lastNodeVisited;
                        curr = null;
                    }
                }
            }
        }

        public static IEnumerable<Node<T>> BreadthFirstTraversalQueue(Node<T> node)
        {
            if (node == null) yield break;

            yield return node;
            IQueue<Node<T>> queue = GetQueueImpl();
{'fraction_non_alphanumeric': 0.08398522381573229, 'fraction_numerical': 0.0010864841373315949, 'mean_word_length': 1.2506112469437654, 'pattern_counts': {'":': 0, '<': 87, '<?xml version=': 0, '>': 93, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2975107', 'n_tokens_mistral': 2398, 'n_tokens_neox': 2240, 'n_words': 525}