Given a binary tree with node structure containing an extra pointer called sib (for sibling) which is currently set to garbage value, write a function which sets the sib pointer to it's immediate right node in the same level. If such node doesn't exist, set sib to null.
O->null / \ O-->O->null / / \ O-->O-->O->null /
O->null
void SetTreeSib(Node *root)
{
root->sib = nullptr;
SetTreeSibHelper(root);
}
void SetTreeSibHelper(Node *n)
{
if (nullptr == n)
return;
if (nullptr != n->right)
SetNodeSib(n->sib, n->right);
if (nullptr != n->left)
{
if (nullptr != n->right)
n->left->sib = n->right;
else
SetNodeSib(n->sib, n->left);
}
// Note the importance of calling with the right child first
SetTreeSibHelper(n->right);
SetTreeSibHelper(n->left);
}
void SetNodeSib(Node *parentsib, Node *child)
{
while (nullptr != parentsib)
{
if (nullptr != parentsib->left)
{
child->sib = parentsib->left;
return;
}
if (nullptr != parentsib->right)
{
child->sib = parentsib->right;
return;
}
parentsib = parentsib->sib;
}
child->sib = nullptr;
}
Iterative solution, using level-order traversal: public void SetTreeSibIterative<T>(Node<T> n)
{
Queue<Node<T>> q = new Queue<Node<T>>();
q.Enqueue(n);
q.Enqueue(null);
while (q.Count > 0)
{
n = q.Dequeue();
if (n == null)
{
if (q.Count > 1)
q.Enqueue(null);
continue;
}
if (q.Count > 0)
n.sib = q.Peek();
else
n.sib = null;
if (n.left != null)
q.Enqueue(n.left);
if (n.right != null)
q.Enqueue(n.right);
}
}
|
|