Suryaamsh
BAN USERFriends, correct me if I am wrong. Algo goes something like this:
At each stage we keep track of the ancestors of an element in the tree and update the matrix accordingly.
To keep track of ancestors,
+ Take N bit vector. It stores ancestors of current element (say "c") with bit 1 in "x"th position of vector implies we should make matrix[x][c] = 1. We should use it across all the recursive calls that follow. If space is not a issue, we can use a N sized array to store the same.
+ Traverse the tree in pre-order [ Root - Left - Right ]
recursion goes something like this: [ very abstract pseudo code ]
processNode( node, &vector){
//set matrix[j][node] = 1 for all j whose position is set to 1
// ( we can use bit-wise operation to find all the bit positions with bit set to 1, it is very standard procedure. Refer internet)
if (no childs) return;
// set the bit at "node"th position in vector to be used for its childs to update matrix
if (left)
processNode(node->left, &vector); // vector is updated here
if(right)
processNode(node->right, &vector);
//reset the "node"th position bit to 0 as we have processed all the child nodes of this node
/* At the end of processing, we have all the nodes updated with information in matrix. */
}
Corner cases might be ignored in the above algo, you are welcome to let me know.
- Suryaamsh December 17, 2012Vandana, it's not the right child always.
The next bigger element will be the successor of the current element in "in-order" traversal of binary tree viz left - root - right.
It may not be performance wise efficient in average case because, sorting the elements in array itself and find the next element performs better. If we use a good sorting algorithm on source array that runs in O(nlog(n)) time, the next bigger element is the next element itself, taking almost no time, compared to finding successor in in-order traversal.
For the benefit of others: we use hash table to look up the elements. To support delete, enqueue and dequeue operations also, we need to know which element is "before" and which one is "after"
- Suryaamsh December 17, 2012We keep track of latest inserted element of hash table [ head ], as well as the the next element to be dequeued [ tail ]
So when we want to enqueue/dequeue, we insert the element in hash table at random position mapped by "hash key" and update the next, previous & also head and tail.
for delete, look up hash table & remove the element entry and update the next, previous pointers ( also head, tail if necessary ).
O(1) complexity depends on the "good"ness of hash algorithm followed. We assume that hash algo is good enough to guarantee O(1) lookup operations.
Doubly linked list is used because, an element need inform its predecessor of insertion as well as successor when it is chosen to be deleted.