<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Rodney Carvalho on Medium]]></title>
        <description><![CDATA[Stories by Rodney Carvalho on Medium]]></description>
        <link>https://medium.com/@rodneycarvalho?source=rss-c7fdc925c0ba------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*Xr0rv2ugfyQrqV14.</url>
            <title>Stories by Rodney Carvalho on Medium</title>
            <link>https://medium.com/@rodneycarvalho?source=rss-c7fdc925c0ba------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 05:05:53 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@rodneycarvalho/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Binary tree breadth-first traversal]]></title>
            <link>https://medium.com/@rodneycarvalho/binary-tree-breadth-first-traversal-111d86e9563a?source=rss-c7fdc925c0ba------2</link>
            <guid isPermaLink="false">https://medium.com/p/111d86e9563a</guid>
            <category><![CDATA[breadth-first-search]]></category>
            <category><![CDATA[ruby]]></category>
            <category><![CDATA[binary-tree]]></category>
            <dc:creator><![CDATA[Rodney Carvalho]]></dc:creator>
            <pubDate>Tue, 04 Aug 2020 20:40:36 GMT</pubDate>
            <atom:updated>2020-08-04T20:47:38.005Z</atom:updated>
            <content:encoded><![CDATA[<p>In this example our goal is to traverse the binary tree and perform an average on the each level of the tree. This is known as breadth-first traversal or level order tree traversal. In terms of time complexity we will have to go through every node of the tree. In Big-O notation this puts us on the order of O(n) complexity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/282/1*GjMdtMrbYIemzs4quoDsew.png" /><figcaption>Sample Binary Tree</figcaption></figure><p>We’re going to start our traversal at the top level, level 0, starting at the value 6. On level 1 we have 3 and 7. One level 2 we have 2 and 5. And finally, level 3 contains 9, 1, 5 and 7. Let’s start with defining a Node class, which has two children and a value</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8a93c943bc94bf9045a2062fe11abe62/href">https://medium.com/media/8a93c943bc94bf9045a2062fe11abe62/href</a></iframe><p>We can define the tree above in code with the following:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6d99bb393ff273fc8dba567f490411e6/href">https://medium.com/media/6d99bb393ff273fc8dba567f490411e6/href</a></iframe><p>The following method loops over each level starting at level 0. The inner loop loops over each node at that level.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d34c54832069bbd675bf460943a8d41c/href">https://medium.com/media/d34c54832069bbd675bf460943a8d41c/href</a></iframe><p>When thinking about space considerations notice that for every level we only keep two things; a list of the values for that level and a running sum of the level. After the traversal of the level we overwrite the list with the new list of the next level as well and compute the average. When storing objects in an array Ruby uses references. So, the maximum memory used at any given time are 2 arrays pointing to the elements in the current level and the next level as well as a value storing the average calculation for each level.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=111d86e9563a" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>