Binary Search Tree Vol. 2

Source code of the examples on Github

Sorting a Binary Search Tree (ASC and DESC)

A binary tree is an unordered data structure, which implies that elements (nodes) are not associated to a consecutive index when they are inserted (unlike lists). However a binary tree can be sorted, it means that its elements can follow a logic sorting criteria.

Then, lets explore a pair of algorithms to sort a BST ascending and descending:

ASCending Sorting

Given the nature of a BST where nodes whose values are less than the root node go to the left, for ascending sorting it is just a matter to print out nodes starting by the leftmost node in the tree onwards. In other words we need to use the inorder traversal algorithm.

1. If the parent node is null then just break the recursion.
2. Look for the leftmost node of the tree in the parent left subtree.
3. You have found the node, then just print out its value.
4. Look for the leftmost node of the BST in the parent right subtree.

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

DESCending Sorting

Now, given that nodes whose values are greater than the root node in a BST go to the right, for descending sorting it is just a matter to print out nodes starting by the rightmost node in the tree onwards. In other words we need to use the inorder traversal algorithm.

1. If the parent node is null then just break the recursion.
2. Look for the rightmost node of the tree in the parent right subtree.
3. You have found the node, then just print out its value.
4. Look for the rightmost node of the BST in the parent left subtree.

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

Lowest Common Ancestor

By definition the lowest common ancestor of 2 nodes x and y is the lowest node which has both as descendants, be aware that a node itself is considered its own descendant.

1. If the parent value is less than x value and y value, it means that we have to look for the LCA in the parent right subtree.
2. If the parent value is greater than x value and y value, it means that we have to look for the LCA in the parent left subtree.
3. Otherwise we have found the LCA then just returns it.

public Node lca(Node parent, Node x, Node y) {
  if(parent.value < x.value && parent.value < y.value) {
    return lca(parent.right, x, y);
  }
  if(parent.value > x.value && parent.value > y.value) {
    return lca(parent.left, x, y);
  }
  return parent;
}