CODEWITHSUNDEEP
javascriptalgorithmrecursiondata-structuresbinary-search-tree
Miguel Gil
Miguel Gil

Reputation: 51

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

Upvotes: 3

Views: 41

Answers (2)

Abhinav Mathur
Abhinav Mathur

Reputation: 8196

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
}

Upvotes: 2

user1984
user1984

Reputation: 6838

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.

Upvotes: 2

Related Questions