getting max value of binary search tree in js

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP



getting max value of binary search tree in js



I'm following along this JS data structures video from udemy on Binary search trees. We've got a method to find the max value through recursion.



I was thinking more of comparing all the numbers such as


BST.prototype.getMaxVal = function()
let num = null;
if (num === null) num = this.value;
else if (this.value > num) num = this.value;
if (this.left) return this.left.getMaxVal();
return num;



but the answer is


BST.prototype.getMaxVal = function()
if (this.right) return this.right.getMaxVal();
else return this.value;



105 is the last number without its own leaf, but this method finds 107 before it? how does it find that without any comparison logic?


function BST(value)
this.value = value;
this.left = null;
this.right = null;


BST.prototype.insert = function(value)
if (value <= this.value)
if (!this.left) this.left = new BST(value);
else this.left.insert(value);
else
if (!this.right) this.right = new BST(value);
else this.right.insert(value);


return this;



const bst = new BST(50);

bst.insert(30);
bst.insert(70);
bst.insert(107);
bst.insert(60);
bst.insert(59);
bst.insert(20);
bst.insert(45);
bst.insert(35);
bst.insert(85);
bst.insert(105);
bst.insert(10);

bst.getMaxVal();



https://repl.it/repls/NumbYellowgreenPlans





Well the comparisons are done in the insert method. Then you know that obj.left will always be lower and obj.right will always be higher.
– Kaiido
Aug 6 at 1:53


insert





right. my question is how does the comparison-less getMaxVal function find the lowest number on obj.right?
– totalnoob
Aug 6 at 2:01






Same as for getMaxVal, since your entry point is bst(50) values that are lower than 50 will be set on the left hand of this object, and if a new value is lower than the previously set lower val, then its own left will hold this new lower val. And in case the entry point is the lowest value, it just returns itself.
– Kaiido
Aug 6 at 2:04



bst





The question is not javascript exclusive. It is a general BST question.
– Mr. Brickowski
Aug 6 at 2:21




3 Answers
3



So this is the visual representation of the BST. If some value is less than you, you pass it on the left, and let the left sub-BST to decide where to put it. If some value is greater than you, pass it on the right sub-BST and let it to decide where to put the value.



enter image description here



In this setup, it is guarantee that, on the left most leaf, it must be the smallest value, and on the right most leaf, it contains the greatest value. Therefore, the idea is about, from every BST point of view, either his left tree has nothing, or its value must be smaller than me. So the algorithms writes:


BST.prototype.getMinVal = function()
// if left tree is not null, it must be smaller tha me. Return its value
if (this.left) return this.left.getMinVal();
// if left tree is null, indicate i'm the smallest available, return me instead.
else return this.value;



Update 1



There is one thing to note. BST is designed to serve the purpose like this. Its data, when doing insertion, is structured to avoid the need of whole tree traversal. Its value is well ordered so you don't have to traverse every node when finding a min/max value. If your algorithms needs to, you are not using it correctly, even the function produce the correct logical output.



By definition an in-order-traversal of a BST will return the sorted values.
The insert() did the comparison and enforced this logic.


insert()



An in-order-traversal is equivalent to scanning the nodes from left to right (you can try this manually). We are not focusing on the leaf nodes. Anything in the left subtree of the 107 node (where 105 resides) are smaller than 107.



Here's your BST:



"value": 50,
"left":
"value": 30,
"left":
"value": 20,
"left": "value": 10, "left": null, "right": null ,
"right": null
,
"right":
"value": 45,
"left": "value": 35, "left": null, "right": null ,
"right": null

,
"right":
"value": 70,
"left":
"value": 60,
"left": "value": 59, "left": null, "right": null ,
"right": null
,
"right":
"value": 107,
"left":
"value": 85,
"left": null,
"right": "value": 105, "left": null, "right": null
,
"right": null





See here for more on BST:
VisuAlgo - Binary Search Tree, AVL Tree



So, if I understand your question correctly, the answer is that, because of the way the binary tree is structured, the getMaxVal and getMinVal methods simply need to go as far to the right or left (respectively) as possible in order to find the correct value. If you look at the insert method, the comparison is already "baked in" to the structure of the "tree" that is created by the series of calls to that method. When we call insert on 105, it will ultimately be placed on in the "right" property of 85, which is itself the "left" property of 107. The getMaxVal function simply takes advantage of the fact that the insert method ensures that no value lower than the greatest value can be inserted to the right of that value. In fact, the greatest inserted value at any point in time will never have anything to it's right, so we can just traverse down the tree to the right until we reach a value that doesn't have a "right" property, and we know that that is the max value in the tree.



Hope that helps!





I didn't see the previous comment until I had already posted my answer - the getMinValue function works the same way, though. It takes advantage of the fact that the insert method can never place anything to the left of the lowest value, unless the thing it is inserting is even lower.
– ace
Aug 6 at 2:04






By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Popular posts from this blog

Firebase Auth - with Email and Password - Check user already registered

Dynamically update html content plain JS

Creating a leaderboard in HTML/JS