Binary Tree Data Structure Vol 2.

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

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).

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.

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.

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.

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.

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.