Need help understanding error in algorithm converting BST to sorted array

Question

Array used to make the BST (that my function takes as an input): [38,95,70,5,10,148,93]

As of now the the function only returns [5,10], instead of returning all elements in a sorted order. What is wrong with this approach?

function sortedArrayFromBST(tree,node,outputArray){
    outputArray=outputArray||[]
    // console.log(tree)
    node=node||tree.root
    console.log(node)
    let left=node.left
    console.log(left)
    let right=node.right
    console.log(right)
    if(left ==null){
        outputArray.push(node.data)
    }else{
        return sortedArrayFromBST(tree,left,  outputArray) 
    }
    
    if(right==null){
        return outputArray
    } else{
        return sortedArrayFromBST(tree, right, outputArray)
    }
 
}

user1984 · Accepted Answer · 2022-08-19 07:24:34Z

2

In the heart of your recursive function you want to do something like the following:

if (node === null) // base case
    return
if (node.left !== null)
    sortedArrayFromBST(node.left, outputArray)
outputArray.push(node.val)
if (node.right !== null)
    sortedArrayFromBST(node.right, outputArray)

return outputArray

Your conditions right now are not correct.

answered Aug 19, 2022 at 7:24

user1984

6,9383 gold badges17 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Miguel Gil Over a year ago

Thank you so much. I still have a hard time understanding recursion in these types of functions. For the simpler stuff I can get them working pretty easily but I struggle a lot here!

Abhinav Mathur · Accepted Answer · 2022-08-19 07:28:18Z

2

The return conditions you're using are wrong. Instead of returning from the left node, you need to append it's values to the output and then process the right node.

function sortedArrayFromBST(tree, node) {
    if (node == null) {
        return []
    }
    outputArray = []

    let left = node.left
    let right = node.right

    outputArray.push(sortedArrayFromBST(tree, left))
    outputArray.push(node.data)
    outputArray.push(sortedArrayFromBST(tree, right))
    return outputArray
}

answered Aug 19, 2022 at 7:28

Abhinav Mathur

8,2363 gold badges14 silver badges26 bronze badges

Collectives™ on Stack Overflow

Need help understanding error in algorithm converting BST to sorted array

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related