We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
You don't actually need to compute all the different BSTs. The trick is to sort the array first.
Then, you iterate through each element in the array and make it the root of a BST.
Then to create the left child and its subtree, you take a subset of the array consisting of everything before the root element. They will all be less than or equal to the root since the array was initially sorted. Recurse on this left subtree.
Same thing for the right child and its subtree, just use everything after the root element in the array to create it.
Your function should have a flag determining whether it's an odd or even row. When you recursively call your function, just toggle this flag. Then, when you add to your total, you'll know based on this flag whether to multiply it by alpha or by beta and -1.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Roy and alpha-beta trees
You are viewing a single comment's thread. Return to all comments →
You don't actually need to compute all the different BSTs. The trick is to sort the array first.
Then, you iterate through each element in the array and make it the root of a BST.
Then to create the left child and its subtree, you take a subset of the array consisting of everything before the root element. They will all be less than or equal to the root since the array was initially sorted. Recurse on this left subtree.
Same thing for the right child and its subtree, just use everything after the root element in the array to create it.
Your function should have a flag determining whether it's an odd or even row. When you recursively call your function, just toggle this flag. Then, when you add to your total, you'll know based on this flag whether to multiply it by alpha or by beta and -1.