In the tree above B and C, and D and E are siblings. So sibling pointer of B should point to C and sibling pointer of D should point to E. Sibling pointer of C and E should be null because they don't have any siblings to the right.
This problem is easily solved using level order traversal as shown below.
class Node { public: Node *left; Node *right;
// Sibling pointer that needs to be set Node *sibling;
// Value stored in the node. For simplicity
// we assume name to be the value std::string name; };
// Fill in the sibling pointer of a binary tree void fill_node_with_next_sbiling(Node *node) { if (!node) return; // Initialize the queue with the root node. std::queue<node> queue; queue.push(node); // Set count of current level in the queue to 1. int cur_count = 1; int child_count = 0; Node *prev = NULL; while (!queue.empty()) { Node *n = queue.front(); queue.pop(); // Set the sibling pointer and set previous as current node if (prev) { prev->sibling = n; prev = n; } else { prev = n; } cur_count--; if (n->left != NULL) { queue.push(n->left); child_count++; } if (n->right != NULL) { queue.push(n->right); child_count++; } // All nodes in the current level are done. // Set the cur_count to next level count // for processing next level if (cur_count == 0) { cur_count = child_count; child_count = 0; prev = NULL; } } }
No comments:
Post a Comment