Right Sibling Tree

Tags

Right Sibling Tree

Category

Binary Trees

Difficulty

Hard

Problem Statement

Given a binary tree (specifically a perfect binary tree where all leaves are at the same depth and every parent has two children), transform it into a "Right Sibling Tree." In this transformation, each node's right pointer should point to its right sibling — the node immediately to its right on the same level of the tree. If a node has no right sibling (it is the rightmost node on its level), its right pointer should be set to null. The left pointers should remain unchanged. The transformation should be done in place.

Intuition

For a perfect binary tree, the right sibling of a left child is always the right child of the same parent. The right sibling of a right child is the left child of the parent's right sibling (if the parent has a right sibling). By processing the tree top-down and setting right sibling pointers at each level, the parent level's sibling information is available when processing the child level.

Approach

  1. Process the tree recursively, starting from the root.
  2. For each node, before modifying pointers, save references to the original left and right children.
  3. If the node has a left child, set the left child's right sibling to be the node's (original) right child.
  4. If the node has a right child and the node itself has a right sibling, set the right child's right sibling to be the right sibling's left child.
  5. If the node has a right child but no right sibling, set the right child's right sibling to null.
  6. Recursively process the left child, then the right child.
  7. Set the current node's right pointer to its right sibling (this was passed down or computed).

Pseudocode

function rightSiblingTree(root):
    mutate(root, null)
    return root

function mutate(node, rightSibling):
    if node is null:
        return

    left = node.left
    right = node.right

    // Process left subtree: left child's right sibling is the right child
    mutate(left, right)

    // Process right subtree: right child's right sibling is the
    // left child of our right sibling (if we have one)
    if rightSibling is not null:
        mutate(right, rightSibling.left)
    else:
        mutate(right, null)

    // Set this node's right pointer to its right sibling
    node.right = rightSibling

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Each node is visited exactly once.
  • Space: O(h) where h is the height of the tree, for the recursion stack. For a perfect binary tree, h = log(n), so the space is O(log n).

Key Insights

  • The transformation must be done carefully: we need the original right child before overwriting the right pointer with the sibling.
  • Processing children before overwriting the current node's right pointer ensures we still have access to the original tree structure.
  • The pattern for the right child's sibling is the key: it crosses family boundaries by linking to the parent's sibling's left child.
  • This only works cleanly for perfect binary trees. For general binary trees, a level-order traversal (BFS) approach is more appropriate.
  • After transformation, the tree's right pointers no longer represent parent-child relationships but rather same-level sibling relationships.

Edge Cases

  • The tree has only a root node — its right pointer is set to null (no sibling).
  • The tree is null — return null.
  • The tree has two levels — left child points to right child, right child points to null, root points to null.
  • Very deep perfect binary trees — recursion depth is O(log n), which is manageable.
  • After transformation, an in-order or pre-order traversal using right pointers will behave differently than before, since the meaning of right has changed.

Linked mentions