BST - 21: Convert BST to Sorted Doubly Linked List (DLL)

Source Code: thecodingsimpl...
Solution
- We traverse the binary tree in inorder manner
- We take a global variable 'prev' & 'headOfList'
- We assign lowest node as headOfList. This is when prev is null.
- When prev is not null, then node.left = prev & prev.right = node
- After each iteration we update the prev to current node
Time Complexity: 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]

[@avikdutta5965]

space complexity cannot be O(1) because there is recursion function for that we required auxiliary space. So space complexity is near about height of the tree, i.e. O(h) [h = height of the tree]

[@lokeshkumarrathinavel6566]

I liked your explanation... made it easy to understand. Actually I solved leet code - 426. Convert Binary Search Tree to Sorted Doubly Linked List - with this explanation. Everything same.. just make it circular, do this.. head.left = prev and prev.right = head. :) Appreciated!!!Thanks Man.

[@CodingSimplified]

Thanks for your nice feedback.

[@harish-wi3ts]

Hi...sir I am unable to solve a single problem in leetcode What are the maths concepts are required...to solve as java developer.sir please do video on this.. or reply me sir. Thanks you.

[@CodingSimplified]

Sure, I'll try to these questions. My suggestion is if you finding in leetcode some difficulty, don't focus much on it but start from basics first. For example, in our playlist we've basics to good questions. Once you've some command on a topic, you can see leetcode questions.

[@saisiddana9345]

sir u missed that headlist .left==null

[@ozanservet]

I think we should count recursive space complexity in the stack and it might be O(n). My solution is below, I am open to comments; Node dLL = null; public void convertBSTToSourtedDoublyLinkedList(Node node) { if(node == null) { return; } convertBSTToSourtedDoublyLinkedList(node.left); if(dLL == null) { dLL = new Node(node.getData()); } else { Node tmp = new Node(node.getData()); dLL.right = tmp; tmp.left = dLL; dLL = dLL.right; } convertBSTToSourtedDoublyLinkedList(node.right); } public void printdLL() { Node node = dLL; System.out.print("printdLL: "); while(node != null) { System.out.print(node.getData() + " "); node = node.left; } System.out.println(); }