Coderust: Hacking the Coding Interview/

...

/

Connect Same Level Siblings of a Binary Tree

Connect Same Level Siblings of a Binary Tree

Given a binary tree, at each level in the hierarchy, connect each node to the one on its right.

We'll cover the following...

Statement

Given a binary tree, connect all nodes at the same hierarchical level. We need to connect them from left to right, such that the next pointer of each node points to the node on its immediate right. The next pointer of the right-most node at each level will be NULL.

For this problem, each node in the binary tree has one additional pointer (the next pointer), along with the left and right pointers.

Example

Let’s consider the following binary tree as an example:

G root 100 node1 50 root->node1 node2 200 root->node2 node3 25 node1->node3 node4 75 node1->node4 node5 125 node2->node5 node6 300 node2->node6 node7 10 node3->node7 node9 15 node8 350 node6->node8 node7->node9

After connecting the nodes at each level, the tree will look like this:

G root 100 node1 50 root->node1 node2 200 root->node2 nullNode1 NULL root->nullNode1 node1->node2 node3 25 node1->node3 node4 75 node1->node4 node5 125 node2->node5 node6 300 node2->node6 nullNode2 NULL node2->nullNode2 node3->node4 node7 10 node3->node7 node9 15 node4->node5 node5->node6 node8 350 node6->node8 nullNode3 NULL node6->nullNode3 node7->node8                               node7->node9 nullNode4 NULL node8->nullNode4 nullNode5 NULL node9->nullNode5

Sample input

The input list below represents the level-order traversal of the binary tree shown above, while the value that follows represents the node whose next node we need to find:

[100, 50, 200, 25, 75, 125, 300, 10, 350, 15], 75

Expected output

Only if the next pointer of the node with value 75 is correctly set up will the correct result, 125, be returned.

125

Try it yourself

Note: The binary tree node’s class has members left and right to store references to other nodes, along with the member data to hold the node’s value.

main.cpp
BinaryTree.cpp
BinaryTreeNode.cpp
#include <iostream>
#include <vector>
#include "BinaryTree.cpp"
using namespace std;
typedef BinaryTreeNode* NodePtr;
void PopulateNextPointers(NodePtr node) {
	// TODO: Write - Your - Code
}
// Do not modify the code below
// Function to find the given node and return its next node
BinaryTreeNode* GetNextNode(BinaryTreeNode* node, int node_data) {
	// Performing Binary Search
	while (node != nullptr && node_data != node->data) {
		if (node_data < node->data) {
			node = node->left;
		} else {
			node = node->right;
		}
	}
	// If node is not found return -1 else return its next node
	if (node == nullptr) {
		BinaryTreeNode* non_existing_node = new BinaryTreeNode(-1);
		return non_existing_node;
	} else {
		return node->next;
	}
}

Solution

We need to connect all nodes at each hierarchical level ...