connect Next Pointers Algorithm
The Connect Next Pointers Algorithm is a technique used in binary trees to establish a connection between the nodes of the same level, creating a linked list-like structure for each level. This is particularly useful in the implementation of advanced tree traversal algorithms and can aid in optimizing the overall performance of tree-based data structures. The algorithm essentially adds an additional "next" pointer to each node in the tree, which links the node to its adjacent sibling on the same level, with a null pointer marking the end of the level. This allows for easy traversal of the tree level by level and can simplify operations that require accessing sibling nodes.
To implement the Connect Next Pointers Algorithm, a level order traversal technique, such as Breadth-First Search (BFS), is employed. BFS uses a queue to store the nodes and traverses the tree in a level-by-level fashion. During the traversal, the algorithm processes each node in the queue, connects it to the next node in the same level, and enqueues its children for further processing. This process is repeated until the queue becomes empty, indicating that all the nodes in the tree have been traversed and connected. The result is a binary tree with next pointers connecting nodes within each level, thus facilitating more efficient and streamlined traversal methods for various tree-based operations.
/**
* Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
*
* Initially, all next pointers are set to NULL.
*
* Note:
*
* You may only use constant extra space.
* You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
*
*/
#include<iostream>
#include<queue>
struct TreeLinkNode {
int data;
TreeLinkNode * left;
TreeLinkNode * right;
TreeLinkNode * next;
TreeLinkNode( int d ) : data{ d }, left{ nullptr }, right{ nullptr }, next{ nullptr } {}
};
void connect(TreeLinkNode *root) {
if( root == nullptr) {
return;
}
std::queue<TreeLinkNode*> qu;
qu.push(root);
qu.push(nullptr);
TreeLinkNode * curr = nullptr;
while(!qu.empty()) {
curr = qu.front();
qu.pop();
if ( curr == nullptr ) {
if (!qu.empty()) {
qu.push(nullptr);
}
continue;
}
if (!qu.empty()) {
curr->next = qu.front();
} else {
curr->next = nullptr;
}
if ( curr->left ) {
qu.push(curr->left);
}
if ( curr->right ) {
qu.push(curr->right);
}
}
}
void printTree( TreeLinkNode * root ) {
if (root) {
std::cout << "Node value " << root->data << "-->";
if ( root->next != nullptr ) {
std::cout << root->next->data << std::endl;
} else {
std::cout << "nullptr" << std::endl;
}
printTree(root->left);
printTree(root->right);
}
}
int main() {
TreeLinkNode * root = new TreeLinkNode(1);
root->left = new TreeLinkNode(2);
root->right = new TreeLinkNode(3);
root->left->left = new TreeLinkNode(4);
root->left->right = new TreeLinkNode(5);
root->right->left = new TreeLinkNode(6);
root->right->right = new TreeLinkNode(7);
std::cout << "Before Connect:\n";
printTree(root);
connect(root);
std::cout << "After Connect:\n";
printTree(root);
return 0;
}
