Search code examples
javascriptalgorithmrecursiondata-structuresbinary-search-tree

Need help understanding error in algorithm converting BST to sorted array


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

Solution

  • 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.