Convert Binary Tree to DLL in-place

How to Convert Binary Tree into DLL in-place. Explain with example

3 Answers
Top Voted Recent Answer
1-3 of  3
3 Answers
Top Voted Recent Answer
  • The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.
    1. If left subtree exists, process the left subtree
    …..1.a) Recursively convert the left subtree to DLL.
    …..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
    …..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
    2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
    …..2.a) Recursively convert the right subtree to DLL.
    …..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
    …..2.c) Make inorder successor as next of root and root as previous of inorder successor.
    3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).
    0
forum   Other Related Discussions
Data Structure

Didn't get the answer.
Contact people of Talent-Data Structure directly by clicking here