I really need this feature in my project. Namely, I have a Red Black Tree and I need to write a function to return all the values higher than X in the sorted order.
Example:
Given the following RBT
function greater(6) should return [ 6, 8, 11, 13, 15, 17, 22, 25, 27]
function greater(11) should return [13, 15, 17, 22, 25, 27]
Any suggestion ? What is the recursion to do it given the fact that I already have found the node X ?
Do an inorder traversal on the tree, when you find a value greater than the given value push it to the result array and return it back.
We don't have to check the left subtree of the current node if the value of the current node is < than the target boundary value. Only check the left subtree if its value is >= target boundary value.
Here is the working example with the Javascript code.
/**
* Function to create a tree node with null left and right child
* @param {Number} val
* @return {Node} tree node
* */
function Node(val) {
this.value = val;
this.left = null;
this.right = null;
}
// Constructing the tree
const root = new Node(13);
root.left = new Node(8);
root.left.left = new Node(1);
root.left.left.right = new Node(6);
root.left.right = new Node(11);
root.right = new Node(17);
root.right.left = new Node(15);
root.right.right = new Node(25);
root.right.right.left = new Node(22);
root.right.right.right = new Node(27);
/**
* In-order traversal of a binary tree.
* While processing the current node, we will check and push the value to result array
* @param {Node} node
* @param {Number} contraint value
* @param {Number[]} result array
* @return {Void}
* */
function inorder(node, val, result) {
if (node == null) return;
/**
* We don't have to check the left subtree of the current node if the value
* of the current node is < than target boundary value. Only check left
* subtree if its value is >= target boundary value.
* */
if(node.value >= val) {
inorder(node.left, val, result);
}
if (node.value > val) {
result.push(node.value);
}
inorder(node.right, val, result);
}
/**
* @param {Node} root
* @param {Number} value
* @return {Number[]} result
* */
function getValuesAfter(root, value) {
const result = new Array();
inorder(root, value, result);
return result;
}
console.log("Sorted values after 6:");
const result6 = getValuesAfter(root, 6);
console.log(result6.join(', '));
console.log("Sorted values after 11:");
const result11 = getValuesAfter(root, 11);
console.log(result11.join(', '));
console.log("Sorted values after 22:");
const result22 = getValuesAfter(root, 22);
console.log(result22.join(', '));