Binary Tree Data Structure Vol. 1
Tags: java, programming, binarytree, algorithms
Published: 2022-12-30 16:57:52

Source code of the examples [on Github](https://github.com/mcwiise/dev.to/blob/main/binary-tree-ds/src/btree/BinaryTree.java).

## What is a Tree?
A tree is a non-linear data structure composed of nodes and edges without cycles. It means that every node in a tree has one and only one edge connecting two nodes:

- **Node**: it is an element that contains a particular information plus the addresses to downward nodes also called children.
- **Edge**: it just connects 2 nodes.

![Simple Tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g3lfzm8o4uve0w57m23m.jpg)

## What is a Binary Tree?
A binary tree is the simplest type of a tree, where nodes can have from zero to 2 children at most.

### Key Concepts
- **Root:** this is the node at the top of the tree.
- **Path:** refers to a sequence of nodes along with the edges.
- **Parent:** every node except for the root node has one edge connecting to an upward node, this one is called parent.
- **Child:** a node below another node connected by one edge is referred as child.
- **Leaf:** a node which does not have any children.
- **Subtree:** all descendants of a node below the root node.
- **Level:** number of edges between the root node and the deepest leaf.
- **Value:** the content of the node also referred as _info._

![Key Concepts Binary Tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cukcrqonhv4kjszz5out.jpg)

## A Brief Intro to Recursiveness
Traversing a binary tree is usually a _**recursive process**_, and I say _usually_ because of there are other alternatives to implement traversing algorithms with _stacks_ or _queues_. However, I consider is better to analyze binary trees from a recursive perspective for academic purposes.

### Recursive Function
A recursive function is no more than a function which calls itself until a condition is meet. Have a look at the following example:

```java
1.  public static void main(String[] args) {
2.    var r = Tales.sillySum(0);
3.    System.out.println(r);
4.  }
5.
6.  public static int sillySum(int acc){
7.    if(acc == 10){
8.      return acc;
9.    } else {
10.     acc++;
11.     return sillySum(acc);
12.   }
13. }
```
Where we can identify 2 key parts of a recursive function:
- _**halting condition:**_ the condition that stops the recursive process (line 7), this is also called the **_base case._**
- _**recursive statement:**_ when the function is called itself (line 11).

## Traversing a Binary Tree
Traversing means to pass through all nodes of a binary tree just one time in a specific order, therefore we can say that every node is a potential **_subtree_** to be traversed, even if it is a **_leaf_**.

Now, lets explore the 3 flavors we have to traverse the binary tree of the chart, and refer to _visit_ as the action of printing out the **_value_** of a node, please keep in mind the 2 key concepts of a recursive function, so you can identify where the recursiveness happens:

### Inorder traversal
1. Traverse all nodes of the _left subtree_ (inorder).
2. Visit the node itself.
3. Traverse all nodes of the _right subtree_ (inorder).

```java
public void inOrderTraversal(Node parent) {
  if (parent == null){
    return;
  } else {
    inOrderTraversal(parent.left);
    System.out.print(parent.value);
    inOrderTraversal(parent.right);
  }
}
```

> Outcome: [4,2,6,5,7,8,1,3]

### Preorder traversal
1. Visit the node itself.
2. Traverse all nodes of the _left subtree_ (preorder).
3. Traverse all nodes of the _right subtree_ (preorder).

```java
public void preOrderTraversal(Node parent) {
  if (parent == null){
    return;
  } else {
    System.out.print(parent.value);
    preOrderTraversal(parent.left);
    preOrderTraversal(parent.right);
  }
}
```

> Outcome: [1,2,4,5,6,7,8,3]

### Postorder traversal
1. Traverse all nodes of the _left subtree_ (postorder).
2. Traverse all nodes of the _right subtree_ (postorder).
3. Visit the node itself.

```java
public void postOrderTraversal(Node parent) {
  if (parent == null){
    return;
  } else {
    postOrderTraversal(parent.left);
    postOrderTraversal(parent.right);
    System.out.print(parent.value);
  }
}
```

> Outcome: [4,6,8,7,5,2,3,1]