Binary Search Tree Vol. 2
Tags: java, binarytree, algorithms, beginners
Published: 2023-01-01 20:48:05

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

## 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._**](https://dev.to/mcwiise/binary-tree-data-structure-253b)

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**_.

```java
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._**](https://dev.to/mcwiise/binary-tree-data-structure-253b)

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**_.

```java
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.

![Lowest common ancestor](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6s671g5miwbruxwd6zep.jpg)

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.

```java
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;
}
```