by Sven Woltmann – May 28, 2021

**Article Series:** Trees

**Part 1: Binary Tree**

(Sign up for the HappyCoders Newsletter

to be immediately informed about new parts.)

Two of the most important topics in computer science are sorting and searching data sets. A data structure often used for both is the binary tree and its concrete implementations binary search tree and binary heap.

In this article, you will learn:

- What is a binary tree?
- What types of binary trees exist?
- How to implement a binary tree in Java?
- What operations do binary trees provide?
- What are pre-order, in-order, post-order, and level-order traversal in binary trees?

You can find the source code for the article in this GitHub repository.

A binary tree is a tree data structure in which each node has at most two child nodes. The child nodes are called *left child* and *right child*.

As an example, a binary tree looks like this:

As a developer, you should know the following terms:

- A
**node**is a structure that contains data and optional references to a left and a right**child node**(or just**child**). - The connection between two nodes is called an
**edge**. - The top node is called the
**root**or**root node**. - A node that has children is an
**inner node**(short:**inode**) and, at the same time, the**parent node**of its child(ren). - A node without children is called an
**outer node**or**leaf node**, or just a**leaf**. - A node with only one child is a
**half node**. Attention: this term exists – in contrast to all others – only for binary trees, not for trees in general. - The number of child nodes is also called the
**degree**of a node. - The
**depth**of a node indicates how many levels the node is away from the root. Therefore, the root has a depth of 0, the root's children have a depth of 1, and so on. - The
**height**of a binary tree is the maximum depth of all its nodes.

The following image shows the same binary tree data structure as before, labeled with node types, node depth, and binary tree height.

Before we get to the implementation of binary trees and their operations, let's first briefly look at some special binary tree types.

In a *full binary tree*, all nodes have either no children or two children.

In a *complete binary tree*, all levels, except possibly the last one, are completely filled. If the last level is not completely filled, then its nodes are arranged as far to the left as possible.

A *perfect binary tree* is a full binary tree in which all leaves have the same depth.

A perfect binary tree of height *h* has *n = 2 ^{h+1}-1* nodes and

At the height of 3, that's 15 nodes, 8 of which are leaves.

In a *balanced binary tree*, each node's left and right subtrees differ in height by at most one.

In a *sorted binary tree* (also known as *ordered binary tree*), the left subtree of a node contains only values less than (or equal to) the value of the parent node, and the right subtree contains only values greater than (or equal to) the value of the parent node. Such a data structure is also called a binary search tree.

For the binary tree implementation in Java, we first define the data structure for the nodes (class Node in the GitHub repository). For simplicity, we use `int`

primitives as node data. We can, of course, use any other or a generic data type; however, with an `int`

, the code is more readable – and that is most important for this tutorial.

```
public class Node {
int data;
Node left;
Node right;
Node parent;
public Node(int data) {
this.data = data;
}
}
```

Code language: Java (java)

The parent reference is not mandatory for storing and displaying the tree. However, it is helpful – at least for certain types of binary trees – when deleting nodes.

The binary tree itself initially consists only of the interface BinaryTree and its minimal implementation BaseBinaryTree, which initially contains only a reference to the root node:

```
public interface BinaryTree {
Node getRoot();
}
public class BaseBinaryTree implements BinaryTree {
Node root;
@Override
public Node getRoot() {
return root;
}
}
```

Code language: Java (java)

Why we bother to define an interface here will become apparent in the further course of the tutorial.

The binary tree data structure is thus fully defined.

An essential operation on binary trees is the traversal of all nodes, i.e., visiting all nodes in a particular order. The most common types of traversal are:

- Depth-first search (pre-order, post-order, in-order, reverse in-order traversal)
- Breadth-first search (level-order traversal)

In the following sections, you will see the different types illustrated by the following example:

We implement the visiting during traversal using the visitor design pattern, i.e., we create a visitor object which we pass to the traversal method.

In depth-first search (DFS), we perform the following three operations in a specific order:

- visiting the current node (from now on referred to as "N),
- the depth-first search is invoked recursively on the left child (referred to as "L"),
- the depth-first search is invoked recursively on the right child (referred to as "R").

The standard sequences are:

In pre-order traversal (also known as NLR), traversing is performed in the following order:

- visiting the current node "N",
- recursive invocation of depth-first search on left subtree "L",
- recursive invocation of depth-first search on right subtree "R".

The nodes of the example tree are visited in the following order, as shown in the diagram below: 3→1→13→10→11→16→15→2

The code for this is fairly simple (DepthFirstTraversalRecursive class, starting at line 21):

```
private void traversePreOrder(Node node, NodeVisitor visitor) {
if (node == null) {
return;
}
visitor.visit(node);
traversePreOrder(node.left, visitor);
traversePreOrder(node.right, visitor);
}
```

Code language: Java (java)

You can either invoke the method directly – in which case you must pass the the root node to it – or via the non-static method `traversePreOrder()`

in the same class (DepthFirstTraversalRecursive, starting at line 17):

```
public void traversePreOrder(NodeVisitor visitor) {
traversePreOrder(tree.getRoot(), visitor);
}
```

Code language: Java (java)

This requires creating an instance of `DepthFirstTraversalRecursive`

, passing a reference to the binary tree to the constructor:

`new DepthFirstTraversalRecursive(tree).traversePreOrder(visitor);`

Code language: Java (java)

An iterative implementation is also possible using a stack (class DepthFirstTraversalIterative from line 20). The iterative implementations are pretty complex, which is why I do not print them here.

You can read why I use `ArrayDeque`

instead of `Stack`

in iterative tree traversals here: Why you should not use Stack.

In post-order traversal (also known as LRN), traversing is performed in the following order:

- recursive invocation of depth-first search on left subtree "L",
- recursive invocation of depth-first search on right subtree "R",
- visiting the current node "N".

In this case, the nodes of the example tree are visited in the following order: 13→1→11→15→2→16→10→3

You can find the code in DepthFirstTraversalRecursive starting at line 42:

```
public static void traversePostOrder(Node node, NodeVisitor visitor) {
if (node == null) {
return;
}
traversePostOrder(node.left, visitor);
traversePostOrder(node.right, visitor);
visitor.visit(node);
}
```

Code language: Java (java)

You can find the iterative implementation, which is even more complicated for post-order traversal than for pre-order traversal, in DepthFirstTraversalIterative starting at line 44.

In-order traversal (also known as LNR) traverses the tree in the following order:

- recursive invocation of depth-first search on left subtree "L",
- visiting the current node "N",
- recursive invocation of depth-first search on right subtree "R".

The nodes of the example tree are visited in the following order: 13→1→3→11→10→15→16→2

You will find the recursive code in DepthFirstTraversalRecursive starting at line 62:

```
public static void traverseInOrder(Node node, NodeVisitor visitor) {
if (node == null) {
return;
}
traverseInOrder(node.left, visitor);
visitor.visit(node);
traverseInOrder(node.right, visitor);
}
```

Code language: Java (java)

See DepthFirstTraversalIterative starting at line 69 for the iterative implementation of in-order traversal.

In a binary search tree, in-order traversal visits the nodes in the order in which they are sorted.

Reverse in-order traversal (also known as RNL) traverses the tree in the following reverse order:

- recursive invocation of depth-first search on right subtree "R",
- visiting the current node "N",
- recursive invocation of depth-first search on left subtree "L".

The nodes of the sample tree are visited in reverse order to the in-order traversal: 2→16→15→10→11→3→1→13

You will find the recursive code in DepthFirstTraversalRecursive starting at line 83:

```
public static void traverseReverseInOrder(Node node, NodeVisitor visitor) {
if (node == null) {
return;
}
traverseReverseInOrder(node.right, visitor);
visitor.visit(node);
traverseReverseInOrder(node.left, visitor);
}
```

Code language: Java (java)

You can find the iterative implementation of reverse in-order traversal in DepthFirstTraversalIterative starting at line 89.

In a binary search tree, reverse in-order traversal visits the nodes in descending sort order.

In breadth-first search (BFS) – also called level-order traversal – nodes are visited starting from the root, level by level, from left to right.

Level-order traversal results in the following sequence: 3→1→10→13→11→16→15→2

To visit the nodes in level-order, we need a queue in which we first insert the root node and then repeatedly remove the first element, visit it, and add its children to the queue – until the queue is empty again.

You can find the code in the BreadthFirstTraversal class:

```
public static void traverseLevelOrder(Node root, NodeVisitor visitor) {
if (root == null) {
return;
}
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
visitor.visit(node);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
```

Code language: Java (java)

You can find examples for invoking all traversal types in the `traverseTreeInVariousWays()`

method of the Example1 class.

Besides traversal, other basic operations on binary trees are the insertion and deletion of nodes.

Search operations are provided by special binary trees such as the binary search tree. Without special properties, we can search a binary tree only by traversing over all nodes and comparing each with the searched element.

When inserting new nodes into a binary tree, we have to distinguish different cases:

Es ist leicht einen neuen Knoten an ein Blatt oder ein Halbblatt anzuhängen. Hierzu müssen wir lediglich die `left`

- oder `right`

-Referenz des Parent-Knotens *P*, an den wir den neuen Knoten *N* anhängen wollen, auf den neuen Knoten setzen. Wenn wir auch mit `parent`

-Referenzen arbeiten, müssen wir diese im neuen Knoten *N* auf den Parent-Knoten *P* setzen.

It is easy to append a new node to a leaf or half leaf. To do this, we just need to set the `left`

or `right`

reference of the parent node *P*, to which we want to append the new node *N*, to the new node. If we are working with a `parent`

reference, we need to set the new node's `parent`

reference to *P*.

But how do you go about inserting a node between an inner node and one of its children?

This is only possible by reorganizing the tree. How exactly the tree is reorganized depends on the concrete type of binary tree.

In this tutorial, we implement a very simple binary tree and proceed as follows for the reorganization:

- If the new node
*N*is to be inserted as a left child below the inner node*P*, then*P*'s current left subtree*L*is set as a left child below the new node*N*. Accordingly, the parent of*L*is set to*N*, and the parent of*N*is set to*P*. - If the new node
*N*is to be inserted as a right child below the inner node*P*, then*P*'s current right subtree*R*is set as a right child below the new node*N*. Accordingly, the parent of*R*is set to*N*, and the parent of*N*is set to*P*.

The following diagram shows the second case: We insert the new node *N* between *P* and *R*:

This is – as mentioned – a very simple implementation. In the example above, this results in a highly unbalanced binary tree.

Specific binary trees take a different approach here to maintain a tree structure that satisfies the particular properties of the binary tree in question (sorting, balancing, etc.).

Here you can see the code for inserting a new node with the given `data`

below the given `parent`

node to the specified `side`

(left or right) using the reorganization strategy defined in the previous section (class SimpleBinaryTree starting at line 18).

(The switch expression with the curly braces was introduced in Java 12/13.)

```
public Node insertNode(int data, Node parent, Side side) {
var node = new Node(data);
node.parent = parent;
switch (side) {
case LEFT -> {
if (parent.left != null) {
node.left = parent.left;
node.left.parent = node;
}
parent.left = node;
}
case RIGHT -> {
if (parent.right != null) {
node.right = parent.right;
node.right.parent = node;
}
parent.right = node;
}
default -> throw new IllegalStateException();
}
return node;
}
```

Code language: Java (java)

In the `createSampleTree()`

method of the Example1 class, you can see how to create the sample binary tree from the beginning of this article.

Also, when deleting a node, we have to distinguish different cases.

If the node *N* to be deleted is a leaf, i.e., has no children itself, then the node is simply removed. To do this, we check whether the node is the left or right child of the parent *P* and set *P*'s `left`

or `right`

reference to `null`

accordingly.

If the node *N* to be deleted has a child *C* itself, then the child moves up to the deleted position. Again, we check whether node *N* is the left or right child of its parent *P*. Then, accordingly, we set the `left`

or `right`

reference of *P* to *N*'s child *C* (the previous grandchild) – and *C*'s parent reference to *N*'s parent *P* (the previous grandparent node).

How to proceed if you want to delete a node with two children?

This requires a reorganization of the binary tree. Analogous to insertion, there are again different strategies for deletion – depending on the concrete type of binary tree. In a heap, for example, the last node of the tree is placed at the position of the deleted node and then the heap is repaired.

We use the following easy-to-implement variant for our tutorial:

- We replace the deleted node
*N*with its left subtree*L*. - We append the right subtree
*R*to the rightmost node of the left subtree.

We can see clearly how this strategy leads to a severely unbalanced binary tree. Specific implementations like the binary search tree and the binary heap, therefore, have more complex strategies.

The following method (class SimpleBinaryTree starting at line 71) removes the passed node from the tree. Corresponding comments mark cases A, B, and C.

```
public void deleteNode(Node node) {
if (node.parent == null && node != root) {
throw new IllegalStateException("Node has no parent and is not root");
}
// Case A: Node has no children --> set node to null in parent
if (node.left == null && node.right == null) {
setParentsChild(node, null);
}
// Case B: Node has one child --> replace node by node's child in parent
// Case B1: Node has only left child
else if (node.right == null) {
setParentsChild(node, node.left);
}
// Case B2: Node has only right child
else if (node.left == null) {
setParentsChild(node, node.right);
}
// Case C: Node has two children
else {
removeNodeWithTwoChildren(node);
}
// Remove all references from the deleted node
node.parent = null;
node.left = null;
node.right = null;
}
```

Code language: Java (java)

The `setParentsChild()`

method checks whether the node to be deleted is the left or right child of its parent node and replaces the corresponding reference in the parent node with the child node. `child`

is `null`

if the node to be deleted has no children, and accordingly, the `child`

reference in the parent node is set to `null`

.

In case the deleted node is the root node, we simply replace the `root`

reference.

```
private void setParentsChild(Node node, Node child) {
// Node is root? Has no parent, set root reference instead
if (node == root) {
root = child;
if (child != null) {
child.parent = null;
}
return;
}
// Am I the left or right child of my parent?
if (node.parent.left == node) {
node.parent.left = child;
} else if (node.parent.right == node) {
node.parent.right = child;
} else {
throw new IllegalStateException(
"Node " + node.data + " is neither a left nor a right child of its parent "
+ node.parent.data);
}
if (child != null) {
child.parent = node.parent;
}
}
```

Code language: Java (java)

In case C (deleting a node with two children), the tree is reorganized as described in the previous section. This is done in the separate method `removeNodeWithTwoChildren()`

:

```
private void removeNodeWithTwoChildren(Node node) {
Node leftTree = node.left;
Node rightTree = node.right;
setParentsChild(node, leftTree);
// find right-most child of left tree
Node rightMostChildOfLeftTree = leftTree;
while (rightMostChildOfLeftTree.right != null) {
rightMostChildOfLeftTree = rightMostChildOfLeftTree.right;
}
// append right tree to right child
rightMostChildOfLeftTree.right = rightTree;
rightTree.parent = rightMostChildOfLeftTree;
}
```

Code language: Java (java)

In the `deleteSomeNodes()`

method of the Example1 class, you can see how some nodes of the example tree are deleted again.

Finally, I want to show you an alternative representation of the binary tree: storing it in an array.

The array contains as many elements as a perfect binary tree of the height of the binary tree to be stored, i.e., *2 ^{h+1}-1* elements for height

The nodes of the tree are sequentially numbered from the root down, level by level, from left to right, and mapped to the array, as shown in the following illustration:

For a complete binary tree, we can trim the array accordingly – or store the number of nodes as an additional value.

Storing a binary tree as an array has the following advantages:

- Storage is more compact, as references to children (and parents, if applicable) are not required.
- Nevertheless, you quickly get from parents to children and vice versa:

For a node at index*i*,- the left child is at index
*2i+1*, - the right child is at index
*2i+2*,

- the parent node is at index
*i/2, rounded down*.

- the left child is at index
- You can perform a level-order traversal by simply iterating over the array.

Against these, one must weigh the following disadvantages:

- If the binary tree is not complete, memory is wasted by unused array fields.
- If the tree grows beyond the array size, the data must be copied to a new, larger array.
- As the tree shrinks, the data should be copied (with some margin) to a new, smaller array to free up unused space.

In this article, you learned what a binary tree is, what types of binary trees exist, what operations you can apply to binary trees, and how to implement a binary tree in Java.

If you liked the article, feel free to share it using one of the share buttons below. Do you want to be informed when the next article is published? Then click here to sign up for the HappyCoders newsletter.

About the author

I'm a freelance software developer with more than two decades of experience in scalable Java enterprise applications. My focus is on optimizing complex algorithms and on advanced topics such as concurrency, the Java memory model, and garbage collection.
Here on HappyCoders.eu, I want to help you become a better Java programmer. Read more about me here.

Well explained with examples and program. Well Done. I appreciate your writing skills.

Thank you, this tutorial very useful.