We know that there are 3 different ways to traverse a Binary Tree i.e. InOrder, PreOrder, and PostOrder. Let us try to ignore other traversals like LevelOrder etc for now. Each traversal has its own significance and you can never think of one traversal technique as a replacement for the other. I am going to talk here about which traversal suits better when the tree is getting distorted. I will be taking 2 examples here and proceed.
The links to left and right subtrees are as important to a tree as the next pointer for a linked list. These are all the pointers/references that keep the structure intact. Once they are lost, there is no way to recover them once again. So when it comes to distorting a tree, I would always prefer PostOrder traversal where you don't touch the current node till you are done with the sub-trees.
Deleting a Binary tree
Consider for example the problem of how to deallocating an entire Binary tree? You cant start with the root node of the tree, as if you do so, you have no way to go to the left and right subtrees. So if you deallocate the root first, you cant proceed anymore. Similarly in case of InOrder traversal, you cant deallocate the right subtree. So the most suitable procedure involves deallocating the left and right subtrees first and coming to the root at last.
Binary tree to Doubly Linked List
Now consider the problem of converting a Binary Tree into a doubly linked list where the left pointer of the tree should be made to point the InOrder predecessor node and right pointer should be altered to point the InOrder successor node.
Though the problem talks about InOrder arrangement, you should not start tackling the problem with InOrder traversal. Because as we discussed in case of delete operation, any operation that distorts the tree is best done by the PostOrder traversal.
So, you need to write a recursive procedure to convert a tree to a Doubly Linked List. You can recursively apply the procedure to the left sub-tree and get a leftDll and separately to the right sub-tree to get a rightDll.
Now, you need to form a single DLL from the leftDll, the current root node, and the rightDll. So you need to attach the last node of the leftDll to the root, and then attach the root to the rightDll's head. However, finding the last node of leftDll is O(n) operation. In order to minimize that, instead of returning a Dll, always return a circular DLL so that once you have access to its head, it is just a O(1) operation to get its tail.
Now, we have discussed that circular DLL is the best data-structure to be returned. But what exact node would you return? Remember that you expect the left subtree to return a circular DLL which is arranged InOrder. Now to preserve the InOrder property, you would want to attach the current root to the end of the Circular DLL. Similarly you would link the circular DLL that you have obtained from the right subtree and form a single circular DLL. Now you should return the head node in other words, the node returned by the left subtree's iteration if present or else the current node to maintain the invariant.
The links to left and right subtrees are as important to a tree as the next pointer for a linked list. These are all the pointers/references that keep the structure intact. Once they are lost, there is no way to recover them once again. So when it comes to distorting a tree, I would always prefer PostOrder traversal where you don't touch the current node till you are done with the sub-trees.
Deleting a Binary tree
Consider for example the problem of how to deallocating an entire Binary tree? You cant start with the root node of the tree, as if you do so, you have no way to go to the left and right subtrees. So if you deallocate the root first, you cant proceed anymore. Similarly in case of InOrder traversal, you cant deallocate the right subtree. So the most suitable procedure involves deallocating the left and right subtrees first and coming to the root at last.
Binary tree to Doubly Linked List
Now consider the problem of converting a Binary Tree into a doubly linked list where the left pointer of the tree should be made to point the InOrder predecessor node and right pointer should be altered to point the InOrder successor node.
Though the problem talks about InOrder arrangement, you should not start tackling the problem with InOrder traversal. Because as we discussed in case of delete operation, any operation that distorts the tree is best done by the PostOrder traversal.
So, you need to write a recursive procedure to convert a tree to a Doubly Linked List. You can recursively apply the procedure to the left sub-tree and get a leftDll and separately to the right sub-tree to get a rightDll.
Now, you need to form a single DLL from the leftDll, the current root node, and the rightDll. So you need to attach the last node of the leftDll to the root, and then attach the root to the rightDll's head. However, finding the last node of leftDll is O(n) operation. In order to minimize that, instead of returning a Dll, always return a circular DLL so that once you have access to its head, it is just a O(1) operation to get its tail.
Now, we have discussed that circular DLL is the best data-structure to be returned. But what exact node would you return? Remember that you expect the left subtree to return a circular DLL which is arranged InOrder. Now to preserve the InOrder property, you would want to attach the current root to the end of the Circular DLL. Similarly you would link the circular DLL that you have obtained from the right subtree and form a single circular DLL. Now you should return the head node in other words, the node returned by the left subtree's iteration if present or else the current node to maintain the invariant.
No comments:
Post a Comment