How to find the longest path in binary search tree using Javascript?

Question

Im trying to figure out how to find the longest path in a binary search tree (not really experienced with bst and recursion) and found a solution which i simply dont understand.

const height = (node) => {
  if(!node) return 0;
  var leftHeight = height(node.left);
  var rightHeight = height(node.right);
  return Math.max(leftHeight, rightHeight) + 1;
}
height(node)

Where is the counter ? As I see it, in leftHeight and rightHeight would be stored the last value. How is it possible that without counting each value, it does count?
Where do I actually return the value? I return the final result --> Math.max(leftHeight, rightHeight) but where do I add, save, return the values in each recursive call ?

An explanation would be truly amazing! THANKS!

Can you, please, give us a 'node' so we can figure out the data you working on ? — ThS
– ThS, Commented Sep 6, 2018 at 22:32

Lux · Accepted Answer · 2018-09-06 22:39:53Z

Basically at some point your callstack will be the longest path.

so lets take this tree:

  A
 / \
B   C
   / \
  D   E

here as JS:

{
    name: 'A'
    left: {
        name: 'B',
        left: null,
        right: null,
    }
    right: {
        name: 'C',
        left: {
            name: 'D',
            left: null,
            right: null,
        },
        right: {
            name: 'E',
            left: null,
            right: null,
        }
    }
}

Then you do node(nodeA). From now on I will use nodeX to reference to the object for the node X.

then height(node.left); will be executed, and because node.left is nodeB this is basically height(nodeB). So your callstack is then this:

height(nodeA)
height(nodeB)

now height(node.left); is executed (node is now nodeB). and because left of nodeB is null this is essentially height(nodeB). Your callstack is then this:

height(nodeA)
height(nodeB)
height(null)

now the line if(!node) return 0; will immediately return from the function, because node is null and so !node is true. The return will be 0 as specified.

The callstack is now again this (the last stack element was removed):

height(nodeA)
height(nodeB)

and the value leftHeight will now be 0 (because thats what was just returned). The line var rightHeight = height(node.right); will essentially do the same, because node.right is also null. So Math.max(leftHeight, rightHeight) is essentially Math.max(0, 0) and so 0. This plus 1 is one. This will be returned. The callstack is now like this:

height(nodeA)

and leftHeight has the value 1 which is correct.

The same happens now for the right side, so for C. Here however node.left will not be null but nodeD, and so another stack frame will be build:

height(nodeA)
height(nodeC)
height(nodeD)

here nodeD has null for left and right and will return 1, identical to nodeB. The same happens to nodeE. Then nodeC then will have leftHeight to be 1 and rightHeight to be one. This plus 1 is 2, so height(nodeC) will return 2.

Then the height(nodeA) will have leftHeight to be 1 and rightHeight to be 2. So Math.max(leftHeight, rightHeight) + 1; is 3 and the correct result.

Basically your code is counting, and the +1 is the counting. The starting point for the counts is always the return 0.

Collectives™ on Stack Overflow

How to find the longest path in binary search tree using Javascript?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related