Learn
BAN USERHere next higher node means that the nearest node whose value is greater than the value at the current node. Not sure sorting would be good here.
The algo to find the maximum area rectangle in histogram can be applied here. Keep pushing in the stack if the next node is of lesser value. When you find a node with greater value pop from stack until the top of stack has value >= the current node. All the popped nodes would have the high pointer point to the current node. Push the current node to the stack.
Since each element is pushed and popped once, you get O(n) complexity.
Move the first pointer to just the byte before the second pointer.
Now check the value. If it's between 0 to 127 then either way it is the last byte. Hence if the second pointer is > 128 then it is the first byte of the two byte word else is the one byte word.
if the value of first pointer is >128 then the second pointer is definitely the second byte of the two byte word.
From what I understand the problem to be you are almost correct.
- Learn July 15, 2014Initialize:
parent pointer = current node
grandparent = parent of parent pointer.
Algorithm.
1. Keep moving to the parent until you find a parent , grandparent pair such that grandfather->left = parent. ( you have to maintain the level as you go up )
2. Move to right of grandparent. level-- ( if no right child repeat 1)
3. Find the first child of the grandparent whose level is same as that of node. you travel the left subtree first and then the right to ensure that nearest node is captured first.
4. If there is no node repeat step 1 until we reach parent.