/*
This function processes Binary Tree as show below
1
2 3
4 5
to circular doubly linked list as shown
4 <-> 2 <-> 5 <-> 1 <-> 3->->->->
Also links to 4 and 3 are updated.
*/
public void convertBTToCDLL(Node current, Node toReturnHead, Node toReturnTail)
{
// Exit conditions and Null handling here.
if( current == null )
{
return;
}
// convert left sub tree to CDLL
Node leftSubTreeHead=null;
Node leftSubTreeTail=null;
if( current->left )
{
convertBTToCDLL(current->left, leftSubTreehead, leftSubTreeTail);
}
// convert right sub tree to CDLL
Node rightSubTreeHead=null;
Node rightSubTreeTail=null;
if(current->right)
{
convertBTToCDLL(current->right, rightSubTreeHead, rightSubTreeTail);
}
// Convert the current node to CDLL
if(! leftSubTreeTail)
{
leftSubTreeTail = leftSubTreeHead = current;
}
if(! rightSubTreeHead)
{
rightSubTreeHead = rightSubTreeTail = current;
}
leftSubTreeTail->right = current;
current->left = leftSubTreeTail;
rightSubTreeHead->left = current;
current->right = rightSubTreeHead;
// Make this circular
toReturnHead = leftSubTreeHead;
toReturnTail = rightSubTreeTail;
}
This function processes Binary Tree as show below
1
2 3
4 5
to circular doubly linked list as shown
4 <-> 2 <-> 5 <-> 1 <-> 3->->->->
Also links to 4 and 3 are updated.
*/
public void convertBTToCDLL(Node current, Node toReturnHead, Node toReturnTail)
{
// Exit conditions and Null handling here.
if( current == null )
{
return;
}
// convert left sub tree to CDLL
Node leftSubTreeHead=null;
Node leftSubTreeTail=null;
if( current->left )
{
convertBTToCDLL(current->left, leftSubTreehead, leftSubTreeTail);
}
// convert right sub tree to CDLL
Node rightSubTreeHead=null;
Node rightSubTreeTail=null;
if(current->right)
{
convertBTToCDLL(current->right, rightSubTreeHead, rightSubTreeTail);
}
// Convert the current node to CDLL
if(! leftSubTreeTail)
{
leftSubTreeTail = leftSubTreeHead = current;
}
if(! rightSubTreeHead)
{
rightSubTreeHead = rightSubTreeTail = current;
}
leftSubTreeTail->right = current;
current->left = leftSubTreeTail;
rightSubTreeHead->left = current;
current->right = rightSubTreeHead;
// Make this circular
toReturnHead = leftSubTreeHead;
toReturnTail = rightSubTreeTail;
}
No comments:
Post a Comment