Binary Trees (Part 1) - The Basics
Tags: codenewbie, todayilearned, datastructures, trees
Published: 2019-11-13 21:10:09

*After a few surprise encounters with binary trees last week, I thought it'd be good for me to finally get more familiar with them so that later I can tackle binary tree problems with more confidence and less angst.*

*This is simply an introduction to trees and the different parts that make up the structure. I also touch on what various binary tree structures can look like and why trees, especially binary trees, are applicable and useful.*

## What are Binary Trees?
![A tree once torn out of the ground planted upside down on its branches](https://images.fineartamerica.com/images-medium-large-5/upside-down-tree-marty-kugler.jpg) 
##### <center>Behold, a perfect specimen of the tree data structure in its natural habitat, shot by [Marty Kugler](https://fineartamerica.com/featured/upside-down-tree-marty-kugler.html)</center>

A **tree** is a data structure that looks like an upside-down tree consisting of nodes. A **binary tree** is a structure of nodes that each point to no more than two children.
***

## The Physiology of a Tree

<img src="https://media.giphy.com/media/cPg6XJTNxDlhQz8zen/giphy.gif" width=500 alt="Image of a basic binary tree structure and a subtree">

A **tree** is a structure composed of **nodes** that each contains a value or data. The **root** is a single node located at the top of the tree. It is the start of the tree where nodes point to child nodes connected by branchlets called **edges**. A **subtree**, much like a clipping, is a subsection or part of a tree.

*** 

<img src="https://media.giphy.com/media/TJglzdRKOELC3W12mZ/giphy.gif" width=500 alt="Three nodes connected, a parent and its two children">


The root of this tree is the **parent** of two **child** nodes, each either a left or a right child. Two children or sub-trees of a shared parent are **siblings**. It's possible for a child to also be the parent of two other child nodes further down the branch. 

***

<img src="https://media.giphy.com/media/KezoursDTpXWUjG3PO/giphy.gif" width=500 alt="Image illustrating the relationship between ancestor and descendant nodes">

As we follow a branch down from a parent node, any other node located down that branch is its **descendent**. And if we follow a branch upwards from a child node, any node up that branch is an **ancestor** of the child node. 

***

<img src="https://thepracticaldev.s3.amazonaws.com/i/xk1qnu5mdxow8a58zzow.png" width="500" alt="A tree showing internal nodes that have children, and external nodes that have no children">

At the bottom or terminal of a branch is the **leaf** or **external node**, which has no children. Nodes that branch further to one or more child nodes are **branch** or **internal nodes**.

***

## Describing a Binary Tree

When we describe a binary tree, we can discuss its **height** or its **depth**. 

<img src="https://thepracticaldev.s3.amazonaws.com/i/6qwyiiz5i0zuufy2lhhg.png" width=500 alt="A view of a tree and each node's depth from the root">

When we talk about a node's depth, we're specifying how many branches or levels down a node is from the root. 

![A step by step view of a tree increasing in height as new levels of nodes are added](https://media.giphy.com/media/MY1IngRAdaHVuNQbSu/giphy.gif)

However, when we talk about height, we can either describe the height of a node or the height of the tree. In both cases, we're describing the distance from an external node to the node or root. 

***

## Binary Tree Identification
Binary trees can be structured differently and possess different kinds of characteristics or qualities. 

<img src="https://thepracticaldev.s3.amazonaws.com/i/r2pju3fgkd5vguciusbo.png" width="500" alt="A full binary tree">

A **full** or **strictly binary tree** is structured so that every node possesses either two or no children.

***

<img src="https://thepracticaldev.s3.amazonaws.com/i/87vvozjt3vb4p94equv7.png" width=500 alt="complete binary tree">

A **complete binary tree** is a tree where nodes at every level but the last is required to have two children. On the last level, the children are positioned as far to the left as possible. So, complete binary tree nodes are connected from top to bottom, left to right. 

***

<img src="https://thepracticaldev.s3.amazonaws.com/i/u9ybf23isl86jzdkei89.png" width=500 alt="perfect binary tree">

A **perfect binary tree** is both *full* and *complete*. All the leaf nodes are located at the same depth, and all internal nodes have two children.

***

![Balanced and Unbalanced Binary Tree](https://media.giphy.com/media/iJgItT1WOBadn4NGle/giphy.gif)

A **balanced binary tree** describes a tree where two sibling subtrees don't differ in height by more than one level. If the difference in height is greater than that, then it is unbalanced.

***

<img src="https://thepracticaldev.s3.amazonaws.com/i/fm989bdx4uhs98ey8qv6.png" width=250 alt="Degenerate Tree">

If every node in a tree has only one child, the structure is a **degenerate** or **pathological tree**, and is essentially a linked list.

***

## Why are Binary Trees Useful?
Like the family trees many of us are familiar with, trees are hierarchical and can represent structural relationships in the data. More technological examples and applications of trees can be the DOM or your file directory.

[**Binary Search Trees (BSTs)**](https://dev.to/jenshaw/binary-search-trees-are-the-best-gkk) are especially useful in algorithms because they are naturally sorted, which makes [search, insertion](https://dev.to/jenshaw/binary-search-trees-are-the-best-gkk), and [deletion](https://dev.to/jenshaw/deleting-nodes-in-binary-search-trees-4nhm) of values especially quick and efficient. This is definitely worth diving into in another blog post!

***


For more information on binary trees, check out these other blogs from my 5-part binary tree series!

* [Part 2 - Binary Search Trees (Insertion and Search)](https://dev.to/jenshaw/binary-search-trees-are-the-best-gkk)
* [Part 3 - Node Deletion](https://dev.to/jenshaw/deleting-nodes-in-binary-search-trees-4nhm)
* [Part 4 - Depth-First Traversals](https://dev.to/jenshaw/binary-trees-discussing-in-depth-first-traversals-4a8n)
* [Part 5 - Breadth-First Traversals](https://dev.to/jenshaw/binary-trees-stay-abreast-of-breadth-first-search-3pi7)