bhuleskar
BAN USERTackling this with a modified BFS using marker points. Expecting this to work on any type of tree or graph and not just binary tree.
In your BFS algorithm where pop() and insert back all the elements in the same queue.
modify this to use a pointer in an array so that you don't really remove it but instead just peeks and behaves logically as a queue.
before inserting the all children of the node you just peeked put the marker of #ofChildren.
Also lets start not with a root but something above the root. This makes it very simple. Don't worry if it sounded tricky, see below for simple explanation:
For the given tree:
start
|
A
/ \
B -> C
/ / \
D -> F-> G
/ \
H -> I
Put each element in the queue using markers as below:
1 A 2 BC 1 D 2 FG 2 HI
Read this as : There is 1 node i.e. A, there are 2 children of A: B and C, B has 1 child D,C has 2 child F,G. and so on. You don't need this information anyways, but just incase if you wondering how did I modify the BFS here with some markers but still a BFS if read without markers.
Now use this BFS with markers to build up the neighbors.
//base for root node - no marker and only 1 root node
#ofMarkersToEvaluate = 0;
#ofNodes = 1;
prev = null;
while (!queue.isEmpty()) {
#ofNodes = queue.take()
if (prev == null) {
prev = queue.take();
}
while (#ofNodes > 1) {
nextNode = queue.take();
prev.next = nextNode;
prev = nextNode;
#ofNodes--;
}
// on the same level, preserve the previous node
if (ofMarkersToEvaluate > 0 )
#ofMarkersToEvaluate --;
continue;
}
//reset prev for a new level
prev = null;
}
Keep a deleted bit field in the Node.
struct Node {
int data;
struct Node * next;
int isDeleted;
}
Your function would just set this bit to 1 (isDeleted = 1) when you ask something to delete.
It takes 2 things into consideration.
1. Deleting the last node where there is only 1 node in the LL.
2. Deleting the last node where the random pointer given is itself the last node.
When you traverse the link list later. You can handle these deleted Node blocks in memory:
1. Skip the ones where Node->isDeleted = 1 (not a good option but not wrong either)
2. While traversing at a later point your program would check if any node is marked as deleted and at this time rearrange pointers correctly. (efficient - this is also the technique used in paging where a page is marked as deleted in memory and delayed the deletion on disk)
Nice one!
- bhuleskar July 16, 2015