Connect nodes at same level in BST

Connect nodes at same level

We know that each node of binary search tree has two pointers, one pointing to left child and another to right child. To connect nodes at same level in binary search tree, apart from normal two pointers left and right, there is one additional pointer is stored in each node called next pointer. Next pointer should point to node which is on right side and at same level. Next pointer of right most node points to NULL. For example for below input binary search tree
Connect nodes at same level
Output should be
connect nodes at same level

Connect nodes at same level

First thing which comes in mind is that we are dealing with all nodes on same level. That is nothing but level order traversal of a binary search tree.
One of the approaches to traverse a tree by level order can be doing breadth first traversal of tree. However, it requires extra space for queue to store nodes at same level. Idea is to store all the nodes in queue and then link them together.

Other approach is based upon creation of linked list using push mechanism. New node is pushed at head of the list. Since rightmost node is terminal node of list formed by connecting nodes at same level, we need to first visit rightmost node at each level. Since right most node points to NULL, do not do anything, just return the node pointer. This node is first node added into linked list being created for that specific level.

Now find second to right most node on the same level, be it currentNode and push that into linked list we created just now. How? By pointing next pointer of currentNode to the list which is already created. Repeat this till left most node of that level is visited.

There are two steps to method: First find nodes at same level and then push those nodes in linked list for that level one by one.

Finding nodes at same level is simple as explained in level order traversal of a tree. Only difference will be that instead of traversing left to right, we will traverse right to left. Why? Because we want rightmost node to be visited first for each level.

Each node on same level is just pushed on to linked list, last node pushed being head of linked list. Please refer pushing a node into linked list.

Specific case of this problem can to be connect all leaf nodes of a binary tree using extra next pointer. In here, only base case change as we are not required to go to all levels, as modification is to be done on the last level only. Even that can be optimized by not calculating the height in advance and checking each node if that is leaf node, if yes push that onto linked list.

Connect nodes at same level

#include <stdio.h>
#include <stdlib.h>
 
struct node{
    int value;
    struct node *left;
    struct node *right;
    struct node *next; //new pointer
};
typedef struct node Node;
 
Node * createNode(int value){
 
    Node * newNode =  (Node *)malloc(sizeof(Node));
    newNode->value = value;
    newNode->right = NULL;
    newNode->left = NULL;
    newNode->next = NULL;
    return newNode;
}
Node * addNode(Node *node, int value){
	if(!node){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}
 
#define MAX(a,b)  (a>b) ?(a):(b)
 
int height(Node *root){
	if(!root)
		return 0;
 
	if(!root->left && !root->right)
		return 1;
 
    int lheight = height(root->left);
    int rheight = height(root->right);
 
    return (lheight > rheight ? lheight+1 : rheight +1);
}
 
void connectLevelRec(Node * node, int desired, Node **lastNode){
    if(node == NULL)
        return;
 
    //Node at the given level
    if (desired == 1){
        //Update the next pointer of node 
        node->next = *lastNode;
        //change the last node 
        *lastNode = node;
    }
    // search for the node again at same level
    connectLevelRec(node->right, desired-1, lastNode);
    connectLevelRec(node->left,  desired-1, lastNode);
}
 
void printTreeLevel(Node *root){
    int h = height(root);
    int i;
 
    for(i=1; i<=h+1; i++){
       Node *lastNode = NULL;
       connectLevelRec(root, i, &lastNode);
    }
 
    Node *current = root;
 
    /*Printing has bugs, it just to check if nodes are being
    added correctly */
    while(current){
        Node *temp = current;
        while(temp){
            printf("%d ", temp->value);
            temp= temp->next;
        }
        printf("\n");
        current = current->left;
    }
}
//Driver program
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,6);
	root = addNode(root,3);
	root = addNode(root,2);
	root = addNode(root,1);
	root = addNode(root,7);
	root = addNode(root,5);
	root = addNode(root,9);
 
	printTreeLevel(root);
 
	return 0;
}

There is another approach which does not need calculation of height and storing of last pointer, saving us space. This approach uses the fact that we have already connected nodes at level i before moving to level i+1. At root both the siblings can be easily connected as root->left->next = root->right; 
connect nodes at same level example
We just need to check if the left child is not NULL.

Going down further, that is to root->left, we will do the same thing for children to root->left children. However, the right child’s next will point to the leftmost child of right child of root to start with. How can we traverse to right child of root from current left child. Yes, we have already connected right child of root as next of left child of root.

#include <stdio.h>
#include <stdlib.h>
 
struct node{
    int value;
    struct node *left;
    struct node *right;
    struct node *next; //new pointer
};
typedef struct node Node;
 
Node * createNode(int value){
 
    Node * newNode =  (Node *)malloc(sizeof(Node));
    newNode->value = value;
    newNode->right = NULL;
    newNode->left = NULL;
    newNode->next = NULL;
    return newNode;
}
Node * addNode(Node *node, int value){
	if(!node){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}
 
#define MAX(a,b)  (a>b) ?(a):(b)
 
void connect(Node* p) {
 
  if (!p) return;
 
  if (p->left)
  	p->left->next = p->right;
 
  if (p->right)
    p->right->next = (p->next) ? p->next->left : NULL;
 
  connect(p->left);
  connect(p->right);
}
 
//Driver program
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,6);
	root = addNode(root,3);
	root = addNode(root,2);
	root = addNode(root,1);
	root = addNode(root,7);
	root = addNode(root,5);
	root = addNode(root,9);
 
	connect(root);
 
	return 0;
}

Worst case complexity of above code to connect nodes at same level at binary search tree will be O(n2) where N is number of node, when tree is completely skewed.

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me, please contact us.