.. _BinaryTreeIntro:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "BinaryTreeIntro";ODSA.SETTINGS.MODULE_LONG_NAME = "Binary Trees Chapter Introduction";ODSA.SETTINGS.MODULE_CHAPTER = "Binary Trees"; ODSA.SETTINGS.BUILD_DATE = "2020-07-28 19:15:00"; ODSA.SETTINGS.BUILD_CMAP = true;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='c++';</script>


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


.. 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
   :satisfies: binary tree intro
   :topic: Binary Trees

Binary Trees Chapter Introduction
=================================

:term:`Tree <tree>` structures enable efficient access and efficient
update to large collections of data.
:term:`Binary trees <binary tree>` in particular are widely used and
relatively easy to implement.
But binary trees are useful for many things besides searching.
Just a few examples of applications that trees can speed up include
:term:`prioritizing jobs  <priority queue>`,
:term:`describing mathematical expressions  <expression tree>`
and the syntactic elements of computer programs,
or organizing the information needed to drive
:term:`data compression algorithms  <Huffman codes>`.

This chapter covers terminology used for discussing binary trees,
:term:`tree traversals <tree traversal>`, approaches to implementing
tree :term:`nodes <node>`, and various examples of binary trees.