BST - 22: Construct Balanced BST from given values | Sorted Array to Balanced BST

Source Code: thecodingsimpl...
Solution
Sort the given array
Now take variable start, end, mid
Get middle element & create node using value present at this index
Now recursively call value from start to mid - 1 in left side & mid + 1 to end in right side
At last return the node
Time Complexity: O(nlogn), if array is sorted then Time complexity will be O(n)
Space Complexity: O(1)
For more info, please see the video.
CHECK OUT CODING SIMPLIFIED
/ codingsimplified
★☆★ VIEW THE BLOG POST: ★☆★
thecodingsimpli...
I started my KZbin channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 500+ videos.
★☆★ SUBSCRIBE TO ME ON KZbin: ★☆★
www.youtube.co...
★☆★ Send us mail at: ★☆★
Email: [e-mail]

[@UdhyaKumar-z4d]

nice thank you sir

[@harshitrathi3077]

Great Teaching !! Keep On Uploading.............

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching.

[@adminuser1578]

Thanks for video

[@CodingSimplified]

Glad you liked it. Keep Watching.

[@jacobkn6594]

Does it mean that it’s not possible to construct BBST from unsorted array?

[@ozanservet]

It is accurate quick or merge sort is O(nlogn) but how inorder method can be O(n) I didn't understand. In addition, I don't think space complexity of this solution is O(1). It uses recursive. Why we do not count space complexity of recursive because of stacks? My solution is below, I am open to feedbacks; public Node convertBstToBalancedTree(Node node) { List list = new ArrayList(); inorderList(node, list); return makeBalanced(createNewNode(-1), list); } public Node makeBalanced(Node node, List inordered) { if(inordered.size() == 0) { return null; } int halfSize = inordered.size() / 2; if(inordered.size() % 2 == 1) { halfSize = (inordered.size() - 1) / 2; } node = createNewNode(inordered.get(halfSize)); node.left = makeBalanced(node.left, inordered.subList(0, halfSize)); node.right = makeBalanced(node.right, inordered.subList(halfSize + 1, inordered.size())); return node; }

[@techamet428]

good explanation..keep it up

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching.

[@abhinavagrawal6148]

Hi Coding Simplified. Please tell what keyboard shortcuts you use while debugging your code. Please reply.

[@CodingSimplified]

They're simply Eclipse IDE shortcut. Like while debugging in Eclipse. You'll use F6 to execute a line & F5 to go inside a function. For more info, please see eclipse debug shortcut on google.

[@shouvikdatta6831]

How the space complexity be O(1)? We are making a BST of size n... So, I think it would be O(n)

[@CodingSimplified]

That's right. If you consider node of tree as well then yes It's O(n). Apart than this, we're not using any other extra space.