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