_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4
You will end up with 4 lists:
- 3 -> NULL
- 5 -> 1-> NULL
- 6 -> 2 -> 0->8 -> NULL
- 7->4-> NULL
void SetTreeNext(Node * root)
{
typedef std::pair NodeData;
std::list queue;
int prevLevel = 0;
Node * prevNode;
queue.push_back (NodeData(root, 1));
while (!queue.empty())
{
NodeData data = queue.front();
Node * curNode = data.first;
int curLevel = data.second;
queue.pop_front();
if (curLevel != prevLevel)
{
prevNode = curNode;
}
else
{
prevNode->next = curNode;
}
if (curNode->left)
queue.push_back (NodeData(curNode->left, curLevel +1) );
if (curNode->right)
queue.push_back (NodeData(curNode->right, curLevel +1) );
}
}
Time complicity O(N). Space complicity O(N)
Method 2:
Could we do it without the level information? Yes of course. We could track the number of nodes at current level and previous level. But here we will present a different solution.
Consider we do a normal BFS, the result looks like this:
3-> 5 -> 1 -> 6 -> 2 -> 0 -> 8 -> 7 ->4
If we have a NULL pointer at the end of each level, the BFS will look like this:
3 -> NULL -> 5 -> 1 -> NULL -> 6 ->2 ->0 ->8 -> NULL -> 7 -> 4 -> NULL
The question is can we convert the first BFS result to the next one? Let's do it level by level.
First we have root information stored in the list
3 -> NULL
We keep a current pointer (starts with the first pointer for every level), now it points to 3. We start from this current pointer and put all its children to the end of list; then the current pointer moves to the next pointer until it sees a NULL (end of the current level). At this moment we know we are done to put children of current level at the end of list; we can put a NULL at the end of this.
3 -> NULL -> 5 -> 1 -> NULLRepeat this process we can get the final list. For every node in this list, we can start to chain them. For every NULL node, we start with a new level.
Time complicity O(N). Space complicity O(N)
Method 3:We presented two methods with O(N) time and O(N) space. We could not do any better in terms of time complexity since we need to visit each node at least once. Could we do it better in terms of space? Here is an interesting one with O(1) space.We have a new pointer 'next' in each node. Could this pointer help us in the tree search? Consider at first level we have:root (3) -> NULLFor next level, we started with one of the children of the first level, in this case it is 5 (left child of 3). What is 5's next node? It could have a few possibilities:
- if 5's parent node has a right child, the next node should be parent node's right child
- if the node itself is the right child or the parent does not have aright child (i.e. at third level, 6->2->0->8->NULL, node 2). In this case, we will go to next node of its parent node and find its first child. What if no child? Continue to search the next chain!
Repeat this process we can chain all the nodes at the same level without any additional space.
Check code below
void SetNextNode (node * root)
{
if (!root || (!root->left && ! root->right)) return;
// start node of current level
node * startNode = root->left ? root->left : root->right;
node * parentNode = root;
while (true)
{
// process current level
Node * currentStartNode = startNode;
while (parentNode)
{
// The next child is the right sibling of current node
if (parentNode->left == startNode && parentNode->right)
{
startNode->next = parentNode->right;
startNode = parentNode->right;
}
else if (parentNode->right == startNode ||
(! parentNode->left && !parentNode->right) )
{
// go to next node in parent's chain
parentNode = parentNode->next;
}
else
{
Node * nextNode = parentNode->left ? parentNode->left : parentNode->right;
startNode->node = nextNode;
startNode = nextNode;
}
}
// find first available child in current level
while (currentStartNode && !currentStartNode->left && !currentStartNode->right)
currentStartNode = currentStartNode->next;
if (!currentStartNode) break;
parentNode = currentStartNode;
startNode = parentNode->left? parentNode->left: parentNode->right;
}
}
