Binary Tree and Binary Search Tree
Another super interesting data structure is Binary Search Tree. I was thrilled to learn about it. Just like a regular Tree data structure it has a parent node and parent node has at most 2 children, who in turn can have at most 2 children. The most common task to be performed is to add another node to the Binary Tree or Binary Search Tree or validate it. In the Binary Search Tree every node on the left is the value less than the root node and every node on the right is greater than the value of the root node. BF or DF traversals I mentioned in my previous blog will seem to do the unnecessary work because if we have to solve the algorithm where we have to find out if the tree contains let’s say number 5 while our root node is number 10. First we compare the number given (5) to our root node, if it’s less than the root node we are going to recurse to the left of our Binary Search Tree. If the value we are searching for is greater than our root node we are going to recurse to the right of our Binary Search Tree. I as soon as you see a diagram, it’s available on the internet, all this terminology if it’s new for you becomes very clear. In order to validate the Binary Search Tree we will call the validate function many times to recurse through every node of our tree. We will pass the information to each subsequent call of our validate function. We will add min and max arguments to our function in order to reflect that every node on the left of the Binary Search Tree is the value less than the root node, thus setting our max value, and every node on the right is greater than the value of the root node, thus setting our min value. If our root number is 10 then while recursing to the left of our Binary Search Tree, our max = 10, subsequently while recursing to the right of our Binary Search Tree, our min = 10. Min and max values will be updated with each call, however anytime we move to the left we are not going to update min at all; anytime we move to the right we will not update max at all. We are going to iterate through each node and compare the current node value to our max and our min values. If max is not equal to null and our current node.data value is greater than max value while we are recursing to the left of our Binary Tree — if that is the case — return false because it is not a Binary Search Tree.
if (max !== null && node.data > max) {
return false;
}
While we are recursing to the right of our Binary Tree, if min is not equal to null and our current node data value is less than min value return false because we do not have a Binary Search Tree.
if (min !== null && node.data < min) {
return false;
}
While we are recursing to the left of our Binary Search Tree, we will use the if statement — if there is a node to the left and we will call validate with the node on the left and min value and max value of the current node, if it returns false we need to return false.
if (node.left && !validate(node.left, min, node.data)) {
return false;
}
We will do the same thing while recursing to the right. If we don’t satisfy any of the if statements we will return true. The last if statements while recursing to the left and then right of the Binary Search Tree are like the Fibonacci algorithm — it comes to you after researching and practicing. I personally enjoyed learning Binary Search Tree and I hope you too. Happy Coding!
