Binary Tree Terminology

• Nodes - the values we store
• Edges - the lines between nodes
• Root - topmost node in the tree
• Parent - a node with 0, 1, or 2 children
• Child - a node that represents the left or right descendent of a parent
• Leaf - a node with no children
• Path - the sequence of nodes and edges connecting two nodes

## Introduction to Binary Trees

Up until this point, we’ve been working exclusively with arrays. Now, we’ll begin working with our first data structure, trees.

A tree is a data structure that stores data in a hierarchical way. It consists only of nodes, and edges. Nodes represent the values we store. Edges represent how these values are connected. A tree diagram is generally read from top to bottom.

``````    2
/ \
/   \
1     3
``````

In this tree, the nodes are 2, 1, and 3. The edges are the lines connecting them. In this tree, we have a parent with two children, a left child and a right child.

``````    2 (parent)
/ \
/   \
1     3 (left child, right child)
``````

Binary trees are a subset of trees. Binary trees are very simple. They consist only of nodes, and edges, like all trees. However, in a binary tree, we describe each node as a parent that has 0,1 or 2 children.

In the above small tree, we’d say that 2 is the parent. It has a left child, 1, and a right child, 3. Here, 1 and 3 don’t have any children. When a node has either no left or no right child, we can represent the lack of a child with `null`. The above tree could also be written like this, where `n` represents a null value.

``````      2 (parent)
/ \
/   \
1     3 (child, child)
/ \   / \
n   n n   n
``````

For our purposes, we’ll imagine trees to be objects that store other objects. In this way, the above tree can be written as a series of nested objects.

### Determining the Size of a Binary Tree

Binary Tree Size Terminology

• Depth - The number of edges on the longest path from a node to a leaf node
• Height - The number of edges from a node to the tree’s root node
• Level - The number of edges from a node to the tree’s root node + 1
``````         11
/  \
7    15
/ \   / \
2  8  13  18
``````

What is the depth, height, and level of the node whose value is 7 in the above tree?