Statistics How To

Binary Trees: Definition, Examples

Graph Theory >

Binary Trees are graphs or tree data structures where each node (shown as circles in the graph to the left) has up to a possible two branches (‘children’). These are called the left branch and right branch, or, sometimes, the left child and right child.


Although they are relatively simple structures, binary trees are extremely useful for modeling data. For example, rational numbers can be represented with a variant of the binary tree, called the Calkin–Wilf tree. They can also be used to represent hierarchies, and reflect structural relationships in data. They are flexible; we can move ‘subtrees’ around easily within a tree as needed. They can also be very efficiently searched and analyzed by computer.

Important Definitions for Binary Trees

The top node of a tree (8 in the above image) is called the root node.

Binary tree showing internal nodes (blue) and external nodes (red).

An external node is one without child branches, while an internal node has at least one child branch.

The size of a binary tree refers to the number of nodes it has.

The distance from a node B to the root node is the level of B. The root is at level 0, the root’s children are at level 1, and so on.

The sum of the levels of each of the internal nodes in a tree is called the internal path length of that tree.

The sum of the levels of each of the external nodes in a tree is called the external path length.

The maximum level, among all of the external nodes, is called the height of the tree.

More Terminology of Binary Trees

A tree that has a root node is called a rooted tree. If every node has at most two branches, it becomes a binary tree and is a rooted binary tree.

A full binary tree

A tree where every node (except for the leaves) has 2 branches is called a full binary tree. Full binary trees are sometimes also called proper or plane binary trees.

A tree where all interior nodes have two branches and all nodes with 0 branches (leaf nodes) are at the same level or have the same depth is called a perfect binary tree.

A binary tree which is completely filled—except potentially the bottom level, which is filled from left to right—is called a complete binary tree. Complete binary trees are important because they provide the best ratio between a tree’s height and the number of nodes.

References

Sedgewick & Flajolet. An Introduction to the Analysis of Algorithms. Retrieved November 24 2017 from:
retrieved from http://aofa.cs.princeton.edu/60trees/.
Parlante, N. Binary Trees. Retrieved November 24, 2017 from:
retrieved from http://cslibrary.stanford.edu/110/BinaryTrees.html

------------------------------------------------------------------------------

Need help with a homework or test question? With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field. If you rather get 1:1 study help, Chegg Tutors offers 30 minutes of free tutoring to new users, so you can try them out before committing to a subscription.

If you prefer an online interactive environment to learn R and statistics, this free R Tutorial by Datacamp is a great way to get started. If you're are somewhat comfortable with R and are interested in going deeper into Statistics, try this Statistics with R track.

Comments? Need to post a correction? Please post a comment on our Facebook page.

Check out our updated Privacy policy and Cookie Policy

Binary Trees: Definition, Examples was last modified: June 2nd, 2018 by Stephanie