Connect nodes at same level | GeeksforGeeks
Write a function to connect all the adjacent nodes at the same level in a binary tree
http://leetcode.com/2010/03/first-on-site-technical-interview.html
You may assume that it is a full binary tree (ie, each node other than the leaves has two children.)
The first key to solving this problem is we have the nextRight pointer. Assume that the nextRight pointers are already populated for this level. How can we populate the next level? Easy… just populate by iterating all nodes on this level. Another key to this problem is you have to populate the next level before you go down to the next level, because once you go down, you have no parent pointer, and you would have hard time populating, as I mentioned in the observation I made earlier.
Method 1 (Extend Level Order Traversal or BFS)
When we enqueue a node, we make sure that correct level value for node is being set in queue. To set nextRight, for every node N, we dequeue the next node from queue, if the level number of next node is same, we set the nextRight of N as address of the dequeued node, otherwise we set nextRight of N as NULL.
Method 2 (Extend Pre Order Traversal)
This approach works only for Complete Binary Trees. In this method we set nextRight in Pre Order fashion to make sure that the nextRight of parent is set before its children. When we are at node p, we set the nextRight of its left and right children. Since the tree is complete tree, nextRight of p’s left child (p->left->nextRight) will always be p’s right child, and nextRight of p’s right child (p->right->nextRight) will always be left child of p’s nextRight (if p is not the rightmost node at its level). If p is the rightmost node, then nextRight of p’s right child will be NULL.
Connect nodes at same level using constant extra space - not complete binary tree
An Iterative Solution
The recursive approach discussed above can be easily converted to iterative. In the iterative version, we use nested loop. The outer loop, goes through all the levels and the inner loop goes through all the nodes at every level. This solution uses constant space.
A Recursive Solution
Read full article from Connect nodes at same level | GeeksforGeeks
Write a function to connect all the adjacent nodes at the same level in a binary tree
http://leetcode.com/2010/03/first-on-site-technical-interview.html
You may assume that it is a full binary tree (ie, each node other than the leaves has two children.)
The first key to solving this problem is we have the nextRight pointer. Assume that the nextRight pointers are already populated for this level. How can we populate the next level? Easy… just populate by iterating all nodes on this level. Another key to this problem is you have to populate the next level before you go down to the next level, because once you go down, you have no parent pointer, and you would have hard time populating, as I mentioned in the observation I made earlier.
void connect(Node* p) {
if (!p) return;
if (p->leftChild)
p->leftChild->nextRight = p->rightChild;
if (p->rightChild)
p->rightChild->nextRight = (p->nextRight) ?
p->nextRight->leftChild :
NULL;
connect(p->leftChild);
connect(p->rightChild);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void connect(Node* p) {
if (p == NULL)
return;
if (p->leftChild == NULL || p->rightChild == NULL)
return;
Node* rightSibling;
Node* p1 = p;
while (p1) {
if (p1->nextRight)
rightSibling = p1->nextRight->leftChild;
else
rightSibling = NULL;
p1->leftChild->nextRight = p1->rightChild;
p1->rightChild->nextRight = rightSibling;
p1 = p1->nextRight;
}
connect(p->leftChild);
}
|
When we enqueue a node, we make sure that correct level value for node is being set in queue. To set nextRight, for every node N, we dequeue the next node from queue, if the level number of next node is same, we set the nextRight of N as address of the dequeued node, otherwise we set nextRight of N as NULL.
Method 2 (Extend Pre Order Traversal)
This approach works only for Complete Binary Trees. In this method we set nextRight in Pre Order fashion to make sure that the nextRight of parent is set before its children. When we are at node p, we set the nextRight of its left and right children. Since the tree is complete tree, nextRight of p’s left child (p->left->nextRight) will always be p’s right child, and nextRight of p’s right child (p->right->nextRight) will always be left child of p’s nextRight (if p is not the rightmost node at its level). If p is the rightmost node, then nextRight of p’s right child will be NULL.
void
connect (
struct
node *p)
{
// Set the nextRight for root
p->nextRight = NULL;
// Set the next right for rest of the nodes (other than root)
connectRecur(p);
}
/* Set next right of all descendents of p.
Assumption: p is a compete binary tree */
void
connectRecur(
struct
node* p)
{
// Base case
if
(!p)
return
;
// Set the nextRight pointer for p's left child
if
(p->left)
p->left->nextRight = p->right;
// Set the nextRight pointer for p's right child
// p->nextRight will be NULL if p is the right most child at its level
if
(p->right)
p->right->nextRight = (p->nextRight)? p->nextRight->left: NULL;
// Set nextRight for other nodes in pre order fashion
connectRecur(p->left);
connectRecur(p->right);
}
An Iterative Solution
The recursive approach discussed above can be easily converted to iterative. In the iterative version, we use nested loop. The outer loop, goes through all the levels and the inner loop goes through all the nodes at every level. This solution uses constant space.
* This function returns the leftmost child of nodes at the same level as p.
This function is used to getNExt right of p's right child
If right child of is NULL then this can also be sued for the left child */
struct
node *getNextRight(
struct
node *p)
{
struct
node *temp = p->nextRight;
/* Traverse nodes at p's level and find and return
the first node's first child */
while
(temp != NULL)
{
if
(temp->left != NULL)
return
temp->left;
if
(temp->right != NULL)
return
temp->right;
temp = temp->nextRight;
}
// If all the nodes at p's level are leaf nodes then return NULL
return
NULL;
}
/* Sets nextRight of all nodes of a tree with root as p */
void
connect(
struct
node* p)
{
struct
node *temp;
if
(!p)
return
;
// Set nextRight for root
p->nextRight = NULL;
// set nextRight of all levels one by one
while
(p != NULL)
{
struct
node *q = p;
/* Connect all childrem nodes of p and children nodes of all other nodes
at same level as p */
while
(q != NULL)
{
// Set the nextRight pointer for p's left child
if
(q->left)
{
// If q has right child, then right child is nextRight of
// p and we also need to set nextRight of right child
if
(q->right)
q->left->nextRight = q->right;
else
q->left->nextRight = getNextRight(q);
}
if
(q->right)
q->right->nextRight = getNextRight(q);
// Set nextRight for other nodes in pre order fashion
q = q->nextRight;
}
// start from the first node of next level
if
(p->left)
p = p->left;
else
if
(p->right)
p = p->right;
else
p = getNextRight(p);
}
}
// Sets the nextRight of root and calls connectRecur() for other nodes
void
connect (
struct
node *p)
{
// Set the nextRight for root
p->nextRight = NULL;
// Set the next right for rest of the nodes (other than root)
connectRecur(p);
}
/* Set next right of all descendents of p. This function makes sure that
nextRight of nodes ar level i is set before level i+1 nodes. */
void
connectRecur(
struct
node* p)
{
// Base case
if
(!p)
return
;
/* Before setting nextRight of left and right children, set nextRight
of children of other nodes at same level (because we can access
children of other nodes using p's nextRight only) */
if
(p->nextRight != NULL)
connectRecur(p->nextRight);
/* Set the nextRight pointer for p's left child */
if
(p->left)
{
if
(p->right)
{
p->left->nextRight = p->right;
p->right->nextRight = getNextRight(p);
}
else
p->left->nextRight = getNextRight(p);
/* Recursively call for next level nodes. Note that we call only
for left child. The call for left child will call for right child */
connectRecur(p->left);
}
/* If left child is NULL then first node of next level will either be
p->right or getNextRight(p) */
else
if
(p->right)
{
p->right->nextRight = getNextRight(p);
connectRecur(p->right);
}
else
connectRecur(getNextRight(p));
}