.. _Binary:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Binary";ODSA.SETTINGS.MODULE_LONG_NAME = "Binary Trees Part 1";ODSA.SETTINGS.MODULE_CHAPTER = "Binary Trees"; ODSA.SETTINGS.BUILD_DATE = "2020-08-23 13:21:52"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:



.. odsalink:: AV/Binary/BinExampCON.css

.. odsalink:: AV/Binary/RecursiveDSCON.css
.. 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: Cliff Shaffer


===================
Binary Trees Part 1
===================

Binary Trees Part 1
-------------------

Binary Trees
~~~~~~~~~~~~
   A binary tree is made up of a finite set of nodes that is either
   empty or consists of a node called the root together with two
   binary trees, called the left and right subtrees, which are
   disjoint from each other and from the root.

   Notation: Node, children, edge, parent, ancestor, descendant, path,
   depth, height, level, leaf node, internal node, subtree.

   .. inlineav:: BinExampCON dgm
      :align: center


A Recursive Data Structure
~~~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: ListRecDSCON dgm
      :align: justify

   .. inlineav:: BinRecDSCON dgm
      :align: justify


Binary Tree Node Class
~~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Binary/BinNode
      :tag: BinNode


Question
~~~~~~~~
   * Write a recursive function named **count** that, given the root to a
     binary tree, returns a count of the number of nodes in the
     tree. Function **count** should have the following prototype::

        int count(BinNode root)


Traversals
~~~~~~~~~~
   * Any process for visiting the nodes in some order is called a
     **traversal**.

   * Any traversal that lists every node in the tree exactly once is called
     an **enumeration** of the tree's nodes.

   * Preorder traversal: Visit each node before visiting its children.

   * Postorder traversal: Visit each node after visiting its children.

   * Inorder traversal: Visit the left subtree, then the node, then the
     right subtree.


Preorder Traversal (1)
~~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Binary/Preorder
      :tag: preorder

Preorder Traversal (2)
~~~~~~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/Binary/BTCON.css

   .. inlineav:: preorderCON ss
      :long_name: Preorder Traversal Slideshow
      :output: show


How not to write a traversal
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Binary/Preorder
      :tag: preorder2

   | Problems:
   |    This has a major bug
   |    It puts the focus in the wrong place: Should focus on the
        current node, not the children. This version is therefore more
        complicated. 

Recursion Examples
~~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/Binary/WriteTrav.css

   .. codeinclude:: Binary/Traverse
      :tag: count

   .. inlineav:: BinaryTreeMistakesCON ss
      :long_name: Binary Tree Common Mistakes Slideshow
      :output: show

.. odsascript:: AV/Binary/BinExampCON.js
.. odsascript:: AV/Binary/ListRecDSCON.js
.. odsascript:: AV/Binary/BinRecDSCON.js
.. odsascript:: AV/Binary/preorderCON.js
.. odsascript:: AV/Binary/BinaryTreeMistakesCON.js