Connect All Siblings of a Binary Tree

Data Structures and Algorithms

Statement

Given the root of a perfect binary tree, where each node has an extra pointer next, connect all nodes from left to right. Do so such that each node points to its immediate right sibling, except for the rightmost node which points to the first node of the next level. The next pointer of the last node of the binary tree should be null.

Constraints

• 0 ≤ number of nodes ≤ 500
• -1000 ≤ node.data ≤ 1000

Solution

"""
production algorithm
"""

from data_structures.queue.queue import Queue


class Solution:
    def connect_all_siblings(self, root):
        """
        time complexity O(n)
        space complexity O(n)
        """
        queue = Queue()
        queue.push(root)
        while not queue.empty():
            node = queue.pop()
            if node:
                queue.push(node.left)
                queue.push(node.right)
                node.next = queue.peek()
        return root


class CustomBinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.next = None

"""
unit tests
"""

from unittest import TestCase
from algorithms.bfs.connect_all_siblings_of_binary_tree.solution import Solution, CustomBinaryTreeNode


class SolutionTestCase(TestCase):
    def test_connect_all_siblings(self):
        # Given
        root = CustomBinaryTreeNode(-6)
        root.left = CustomBinaryTreeNode(-15)
        root.right = CustomBinaryTreeNode(7)
        root.left.left = CustomBinaryTreeNode(-18)
        root.left.right = CustomBinaryTreeNode(-11)
        root.right.left = CustomBinaryTreeNode(1)
        root.right.right = CustomBinaryTreeNode(17)
        root.left.left.left = CustomBinaryTreeNode(-19)
        root.left.left.right = CustomBinaryTreeNode(-17)
        root.left.right.left = CustomBinaryTreeNode(-12)
        root.left.right.right = CustomBinaryTreeNode(-8)
        root.right.left.left = CustomBinaryTreeNode(-5)
        root.right.left.right = CustomBinaryTreeNode(6)
        root.right.right.left = CustomBinaryTreeNode(13)
        root.right.right.right = CustomBinaryTreeNode(20)
        solution = Solution()

        # When
        result = solution.connect_all_siblings(root)

        # Then
        numbers = [-6, -15, 7, -18, -11, 1,
                   17, -19, -17, -12, -8, -5, 6, 13, 20]
        current = result
        for number in numbers:
            self.assertEqual(current.data, number)
            current = current.next
        self.assertEqual(current, None)

Strategy

Breadth First Search.

Explanation

First, the algorithm pushes the root node to a queue for breadth first search traversal. For each iteration, a node is popped from the queue. If the node isn’t null, then its children are pushed to the queue. Also, the current node’s next pointer is pointed to the next node in the queue, i.e. the head of the queue. The result is all nodes connected to their immediate right sibling.

Time Complexity

All nodes of the binary tree are visited once. Therefore, the time complexity of the algorithm is O(n).

Space Complexity

All nodes of the current level push all nodes of the next level to the queue. Given that the tree is a perfect binary tree, the last level of the tree has half of all nodes in the tree, which is proportional to n, where n is the number of nodes in the tree. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/bfs/connect_all_siblings_of_binary_tree at main ·…