Write a function to connect all the adjacent nodes at the same level in a binary tree.
Input Tree A / B C / D E F Output Tree A--->NULL / B-->C-->NULL / D-->E-->F-->NULL
We have already discussed O(n^2) time and O approach in Connect nodes at same level as morris traversal in worst case can be O(n) and calling it to set right pointer can result in O(n^2) time complexity.
In this post, We have discussed Level Order Traversal with NULL markers which are needed to mark levels in tree.
Following are populated nextRight pointers in the tree (-1 is printed if there is no nextRight) nextRight of 10 is -1 nextRight of 8 is 2 nextRight of 2 is -1 nextRight of 3 is 90 nextRight of 90 is -1
Time complexity :O(n) where n is the number of nodes
We can also follow the implementation discussed in Print level order traversal line by line | Set 1. We keep connecting nodes of same level by keeping track of prev visited node of same level.
Implementation : https://ide.geeksforgeeks.org/gV1Oc2
Thanks to Akilan Sengottaiyan for suggesting this alternate implementation.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.