Finding minimum value in binary search tree?

JavaScript
1

In the below recursive function why it returns if left child is present?

 BST.prototype.getMinVal = function() {
    if (this.left) return this.left.getMinVal();
    else return this.value;
  };
2

It’s a function called getMinVal. The left value of each branch is the smaller value.

https://i-msdn.sec.s-msft.com/dynimg/IC520.gif

The function returns the left value to keep on working down to smaller and smaller values.

1 Like
3

The question though wasn’t “why left”, but why it returns.

The answer is that a recursive function that’s expected to return a value must return a value in all cases. It’s how the answer ‘walks back up’ your recursive depth.
Let’s take Paul’s tree.
We start at 90, because it’s the only node the outside code knows about.

Start Depth 1 (90):
  If (This Has a Left) = True
   Evaluate right hand side. Right hand side contains a function (getMinVal).
    Start Depth 2 (50):
       If (This Has a Left) = True
       Evaluate right hand side. Right hand side contains a function (getMinVal).
       Start Depth 3 (20):
          If (This Has a Left) = True
          Evaluate right hand side. Right hand side contains a function (getMinVal).         
         Start Depth 4 (5):
             If (This Has a Left) = False
             Return 5.
          End Depth 4
          Right hand side now evaluates to "return 5". Return 5.
      End Depth 3
      Right hand side now evaluates to "return 5". Return 5.
   End Depth 2
   Right hand side now evaluates to "return 5". Return 5.
End Depth 1.
1 Like
4

Thank man got it

5

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.