getting max value of binary search tree in js

Question

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
– Kaiido, Commented Aug 6, 2018 at 1:53
right. my question is how does the comparison-less getMaxVal function find the lowest number on obj.right? — totalnoob
– totalnoob, Commented Aug 6, 2018 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
– Kaiido, Commented Aug 6, 2018 at 2:04
The question is not javascript exclusive. It is a general BST question. — developwoof
– developwoof, Commented Aug 6, 2018 at 2:21

developwoof · Accepted Answer · 2018-08-08 07:30:31Z

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.

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.

leesei · Accepted Answer · 2018-08-06 02:05:43Z

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

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

ace · Accepted Answer · 2018-08-06 02:02:56Z

0

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!

answered Aug 6, 2018 at 2:02

ace

2302 silver badges6 bronze badges

1 Comment

ace Over a year ago

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.

Collectives™ on Stack Overflow

getting max value of binary search tree in js

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related