Binary Tree Data Structure Vol 2.
Tags: programming, java, beginners, algorithms
Published: 2022-12-31 16:16:36

Let's review some problems we can solve by using the traversal algorithms we learnt in previous posts.

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

## Inorder Predecesor
We can use the traversing algorithms to perform some operations in a binary tree, for example we may want to replace every node by its _**inorder predecessor**_, being this the previous node when traversing the binary tree (inorder).

![swap nodes inorder](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9ip426hduk1hp6cl3f09.jpg)

A recursive algorithm should look like this:

1. Define an scoped variable to keep track the predecessors while traversing the binary tree.
2. If the _**parent node**_ is `null`, then just return the node.
3. Otherwise, perform predecessor swapping to the parent left subtree, swap the values, and then perform predecessor swapping to the parent right subtree.

```java
int predecessor = -1;
private void inOrderPredecessorSwap(Node parent){
  if(parent == null){
    return;
  } else {
    this.inOrderPredecessorSwap(parent.left);
    this.swap(parent);
    this.inOrderPredecessorSwap(parent.right);
  }
}
private void swap(Node parent) {
  var temp = parent.value;
  parent.value = predecessor;
  predecessor = temp;
}
```
> Inorder traversal outcome:  6,5,8,7
> After swapping outcome:    -1,6,5,8

## Highest Level of a Binary Tree
The highest level of a tree is represented by the number of edges between the root node and the deepest leaf, then we have:

1. Check if the parent node is `null`, then return -1.
2. Now, calculates the highest level of the _**left subtree**_ and **_the right subtree._**
3. If the highest level of the left subtree is greater than the right subtree, then return the left one plus 1, otherwise return the right one plus 1. 

```java
private int highestLevel(Node parent){
  if(parent == null){
    return -1;
  }
  var hLeft = this.highestLevel(parent.left);
  var hRight = this.highestLevel(parent.right);
  if(hLeft > hRight){
    return hLeft + 1;
  } else {
    return hRight + 1;
  }
}
```
## Copy a Binary Tree
Another application of _**the preorder traversal algorithm**_ is when we need to create a new binary tree by copying all nodes from another one.

1. Check if the parent is null, then just returns it.
2. Else, create a new instance of a node from the parent node.
3. Now, copy the parent left subtree to the recently created node, and do the same with the parent right subtree.
4. Just return the node created.
```java
public Node copy(Node parent){
  if(parent == null){
    return parent;
  } else {
    var newParent = parent;
    newParent.left = this.copy(parent.left);
    newParent.right = this.copy(parent.right);
    return newParent;
  }
}
```

## Deleting a Binary Tree
We can use the **_Postorder traversal algorithm_** to delete all nodes of a binary tree.

1. Check if the parent is `null`, then just returns it.
2. Else, delete the parent left subtree and the parent right subtree.
3. Then, just returns `null.`
```java
public Node delete(Node parent){
  if(parent == null){
    return parent;
  } else {
    this.delete(parent.left);
    this.delete(parent.right);
    return null;
  }
}
```

## Conclusion
There are many other operations we need to perform when working with binary trees, but most of them can be implemented just by applying a variation of the 3 traversal algorithms we have reviewed in this series of posts.