.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Molly


Trees
=========================

Objectives
----------------------

* Describe the Tree ADT, and the characteristics of a Tree and a Binary Tree
* Define Tree terminology including - node, root, edge, parent, child, sibling, leaf, height, level
* Traverse a given Tree using Inorder, Preorder, Postorder, and Level order
* Determine the height and number of nodes of a given Tree
* Implement a Tree ADT as a recursive data structure

Suggested Reading
~~~~~~~~~~~~~~~~~

Chapter 23 Trees & Chapter 24 Tree Implementations from `Data Structures and Abstractions with Java, 4th edition  by Frank M. Carrano and Timothy Henry <https://www.amazon.com/Data-Structures-Abstractions-Java-4th/dp/0133744051/ref=sr_1_1?ie=UTF8&qid=1433699101&sr=8-1&keywords=Data+Structures+and+Abstractions+with+Java>`_

.. _TreeIntro: 

Interactive: Introduction to Trees
-----------------------------------


.. admonition:: Follow Along and Engage

    Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

   .. raw:: html

      <a href="https://courses.cs.vt.edu/cs2114/SWDesignAndDataStructs/course-notes/TreeIntro.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      TreeIntro.pdf</img>
      </a>


.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 38%">
        <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all&id=36fdb68e-69c3-4680-9af4-b42701456498" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="_LABEL_" aria-description="Introduction to Trees"></iframe>
     </div>

Checkpoint 1
------------

.. avembed:: Exercises/SWDesignAndDataStructs/TreesCheckpoint1Summ.html ka
   :long_name: Checkpoint 1

.. _TreeBinTree: 

Interactive: Binary Trees
-------------------------

.. admonition:: Follow Along and Engage

    Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

   .. raw:: html

      <a href="https://courses.cs.vt.edu/cs2114/SWDesignAndDataStructs/course-notes/BinaryTreesIntro.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      BinaryTrees.pdf</img>
      </a>


.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 38%">
        <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all&id=8b33eba1-909d-4b8f-9e4e-b40300c90729" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Binary Trees" aria-description="Binary Trees"></iframe>
     </div>


Checkpoint 2
------------

.. avembed:: Exercises/SWDesignAndDataStructs/TreesCheckpoint2Summ.html ka
   :long_name: Checkpoint 2

.. _TreeTraverse: 

Interactive: Binary Tree Traversals
-----------------------------------


.. admonition:: Follow Along and Engage

    Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

   .. raw:: html

      <a href="https://courses.cs.vt.edu/cs2114/SWDesignAndDataStructs/course-notes/IntroToTraversals.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      IntroToTraversals.pdf</img>
      </a>


.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 38%">
        <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all&id=2fcbb94e-adbb-4a44-93a7-b40e009b4211" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Binary Tree Traversals"" aria-description="Binary Tree Traversals""></iframe>
     </div>


Checkpoint 3
------------

.. avembed:: Exercises/SWDesignAndDataStructs/TreesCheckpoint3Summ.html ka
   :long_name: Checkpoint 3

.. _TreeProg: 

Interactive: Programming Binary Trees
-------------------------------------

.. admonition:: Follow Along and Engage

    Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

   .. raw:: html

      <a href="https://courses.cs.vt.edu/cs2114/SWDesignAndDataStructs/course-notes/ProgrammingTrees.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      ProgrammingTrees.pdf</a>


.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 38%">
        <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all&id=ae5bf4d2-bfd1-47ab-91f8-b3fd00d5f831" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Programming Binary Trees" aria-description="Programming Binary Trees"></iframe>
     </div>