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

*, it means that its elements can follow a logic sorting criteria.*

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

- If the parent node is
`null`

then just break the recursion. - Look for the
node of the tree in the*leftmost*.**parent left subtree** - You have found the node, then just print out its value.
- Look for the
node of the BST in the**leftmost**.**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.*

- If the parent node is
`null`

then just break the recursion. - Look for the
node of the tree in the*rightmost*.**parent right subtree** - You have found the node, then just print out its value.
- Look for the
node of the BST in the*rightmost*.**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

**is the lowest node which has both**

*y**, be aware that a node itself is considered its own descendant.*

**as descendants**- If the
than x value and y value, it means that we have to look for**parent value is less**.**the LCA in the parent right subtree** - If the
than x value and y value, it means that we have to look for**parent value is greater**.**the LCA in the parent left subtree** - 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;
}
```

## Top comments (0)