Need help understanding error in algorithm converting BST to sorted array-CodePudding

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)
    }
 
}

CodePudding user response：

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.

CodePudding user response：

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
}