Connect All Siblings
Problem Statement
Given the root to a binary tree where each node has an additional pointer called sibling (or next), connect the sibling pointer to the next node in the same level. The last node in each level should point to the first node of the next level in the tree.
Consider the following binary tree.
Here’s how the final tree would look when all sibling pointers have been connected.
Hint
- Level order traversal
Try it yourself
void populate_sibling_pointers(BinaryTreeNode* root) {//TODO: Write - Your - Code}
Solution
void populate_sibling_pointers(BinaryTreeNode* root) {if (root == nullptr) {return;}BinaryTreeNode* current = root;BinaryTreeNode* last = root;while (current != nullptr) {if (current->left != nullptr) {last->next = current->left;last = current->left;}if (current->right != nullptr) {last->next = current->right;last = current->right;}last->next = nullptr;current = current->next;}}void reset_siblings(BinaryTreeNode* root) {if (root == nullptr) return;root->next = nullptr;reset_siblings(root->left);reset_siblings(root->right);}int main(int argc, char* argv[]) {BinaryTreeNode* root = create_random_BST(15);display_level_order(root);cout << endl << "level_order_using_next";level_order_using_next(root);cout << endl;reset_siblings(root);populate_sibling_pointers(root);level_order_using_next(root);}
Solution Explanation
Runtime Complexity
Linear, O(n).
Memory Complexity
Constant O(1).
Solution Breakdown
A binary tree is a data structure made up of nodes, where each node contains a “left” reference, a “right” reference, and a data element. The topmost node in the tree is called the root. Every node except the ‘root’ node is connected by a directed edge from exactly one other node. This node is called the parent of that node. On the other hand, each node can be connected to an arbitrary number of nodes, called children. Nodes with the same parent node are called siblings.
Each node in the above binary tree has one more pointer i.e. next along with the left and right pointers. ‘Next’ is used to connect one node to the other. After connecting siblings, a linked-list-like structure is formed whose head is the root node. We keep two pointers current and last. ‘current’ is the node we are working at and ‘last’ is the last node in the linked list already constructed (i.e. siblings already connected). Below are the steps we use to connect all siblings in the tree:
Initially set both current and last as 'root'
while current node is not null
If current node has a left child, append this left node to the last and make it last node.
If current node has a right child, append this right node to the last and make it last node.
update current node to current's next node
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!
