Given a Binary Tree, where each node contains an extra empty pointer initially null. The task is to connect all nodes of the binary tree to their left neighbor at the same level using this extra pointer.
Examples:
Input :
A
/ \
B C
/ \ \
D E F
Output :
NULL<--A
/ \
NULL<--B<--C
/ \ \
NULL<--D<--E<--F
Approach:
We can use the Pre-order traversal of the tree passing the level of the node at each call. The root node is at level 0. While traversing we store the recently seen node at that level in an array of node pointers. The pre-order traversal ensures that the node in the array at a particular level is left neighbor of the upcoming node at the same level.
Below is the implementation of the above approach:
C++
// CPP program to connect nodes// at same level using extended// pre-order traversal#include <bits/stdc++.h>#include <iostream>using namespace std;// Binary tree node, with extra pointer leftNeighbour// to store the neighbour to left nodesclass node {public: int data; node* left; node* right; node* leftNeighbour; /* Constructor that allocates a new node with the given data and NULL left and right pointers. */ node(int data) { this->data = data; this->left = NULL; this->right = NULL; this->leftNeighbour = NULL; }};// Array to store the recent visited // node at particular level represented // by indicesnode* a[100];// Function to connect nodes using preorder // traversalvoid connectNodes(node* p, int l){ if (p == NULL) return; // assigning left neighbor p->leftNeighbour = a[l]; // updating value of the recent // node at level a[l] = p; connectNodes(p->left, l + 1); connectNodes(p->right, l + 1);}// Utility function to connect nodes to neighbours// using preorder traversalvoid connectNodesUtil(node* root){ // Initialize nodes at every level to NULL for (int i = 0; i < 100; i++) a[i] = NULL; // Populates next left pointer in all nodes connectNodes(root, 0); // Let us check the values of next left pointers cout << "Following are populated leftNeighbour" <<" pointers in the tree:\n"; cout << "leftNeighbour of " << root->data << " is " << (root->leftNeighbour ? root->leftNeighbour->data : -1) << endl; cout << "leftNeighbour of " << root->left->data << " is " << (root->left->leftNeighbour ? root->left->leftNeighbour->data : -1) << endl; cout << "leftNeighbour of " << root->right->data << " is " << (root->right->leftNeighbour ? root->right->leftNeighbour->data : -1) << endl; cout << "leftNeighbour of " << root->left->left->data << " is " << (root->left->left->leftNeighbour ? root->left->left->leftNeighbour->data : -1) << endl;}// Driver Codeint main(){ /* Constructed binary tree is 10 / \ 8 2 / 3 */ node* root = new node(10); root->left = new node(8); root->right = new node(2); root->left->left = new node(3); connectNodesUtil(root); return 0;} |
Java
// Java program to connect nodes// at same level using extended// pre-order traversalimport java.util.*;class GFG{// Binary tree node, with extra pointer leftNeighbour// to store the neighbour to left nodesstatic class node { int data; node left; node right; node leftNeighbour; /* Constructor that allocates a new node with the given data and null left and right pointers. */ node(int data) { this.data = data; this.left = null; this.right = null; this.leftNeighbour = null; }}// Array to store the recent visited // node at particular level represented // by indicesstatic node a[] = new node[100];// Function to connect nodes using preorder // traversalstatic void connectNodes(node p, int l){ if (p == null) return; // assigning left neighbor p.leftNeighbour = a[l]; // updating value of the recent // node at level a[l] = p; connectNodes(p.left, l + 1); connectNodes(p.right, l + 1);}// Utility function to connect nodes to neighbours// using preorder traversalstatic void connectNodesUtil(node root){ // Initialize nodes at every level to null for (int i = 0; i < 100; i++) a[i] = new node(-1); // Populates next left pointer in all nodes connectNodes(root, 0); // Let us check the values of next left pointers System.out.println( "Following are populated leftNeighbour" + " pointers in the tree:"); System.out.println( "leftNeighbour of " + root.data + " is " + (root.leftNeighbour != null ? root.leftNeighbour.data : -1)); System.out.println( "leftNeighbour of " + root.left.data + " is " + (root.left.leftNeighbour != null ? root.left.leftNeighbour.data : -1)); System.out.println( "leftNeighbour of " + root.right.data + " is " + (root.right.leftNeighbour != null ? root.right.leftNeighbour.data : -1) ); System.out.println( "leftNeighbour of " + root.left.left.data + " is " + (root.left.left.leftNeighbour != null ? root.left.left.leftNeighbour.data : -1));}// Driver Codepublic static void main(String args[]){ /* Constructed binary tree is 10 / \ 8 2 / 3 */ node root = new node(10); root.left = new node(8); root.right = new node(2); root.left.left = new node(3); connectNodesUtil(root);}}// This code is contributed by Arnab Kundu |
Python3
# Python3 program to connect nodes# at same level using extended# pre-order traversal# Binary tree node, with extra # pointer leftNeighbour to store # the neighbour to left nodesclass node: def __init__(self, x): self.data = x self.left = None self.right = None self.leftNeighbour = None# Array to store the recent visited# node at particular level represented# by indicesa = [None for i in range(100)]# Function to connect nodes using # preorder traversaldef connectNodes(p, l): if (p == None): return # assigning left neighbor p.leftNeighbour = a[l] # updating value of the # recent node at level a[l] = p connectNodes(p.left, l + 1) connectNodes(p.right, l + 1)# Utility function to connect # nodes to neighbours# using preorder traversaldef connectNodesUtil(root): # Populates next left # pointer in all nodes connectNodes(root, 0) # Let us check the values # of next left pointers print("Following are populated" + "leftNeighbour pointers in" + "the tree:") x =- 1 if root.leftNeighbour: x = root.leftNeighbour.data print("leftNeighbour of ", root.data, " is ", x) x =- 1 if root.left.leftNeighbour: x = root.left.leftNeighbour.data print("leftNeighbour of ", root.left.data, " is ", x) x =- 1 if root.right.leftNeighbour: x = root.right.leftNeighbour.data print("leftNeighbour of ", root.right.data, " is ", x) x =- 1 if root.left.left.leftNeighbour: x = root.left.left.leftNeighbour.data print("leftNeighbour of ", root.left.left.data, " is ", x)# Driver Codeif __name__ == '__main__': # /* Constructed binary tree is # 10 # / \ # 8 2 # / # 3 # */ root = node(10) root.left = node(8) root.right = node(2) root.left.left = node(3) connectNodesUtil(root) # This code is contributed by Mohit Kumar 29 |
C#
// C# program to connect nodes// at same level using extended// pre-order traversalusing System;// Binary tree node, with extra pointer leftNeighbour// to store the neighbour to left nodesclass node { public int data; public node left; public node right; public node leftNeighbour; /* Constructor that allocates a new node with the given data and null left and right pointers. */ public node(int data) { this.data = data; this.left = null; this.right = null; this.leftNeighbour = null; }}class GFG{ static node root; // Array to store the recent visited // node at particular level represented // by indices static node[] a = new node[100]; // Function to connect nodes using preorder // traversal static void connectNodes(node p, int l) { if (p == null) { return; } // assigning left neighbor p.leftNeighbour = a[l]; // updating value of the recent // node at level a[l] = p; connectNodes(p.left, l + 1); connectNodes(p.right, l + 1); } // Utility function to connect nodes to neighbours // using preorder traversal static void connectNodesUtil(node root) { // Initialize nodes at every level to null for (int i = 0; i < 100; i++) { a[i] = new node(-1); } // Populates next left pointer in all nodes connectNodes(root, 0); // Let us check the values of next left pointers Console.WriteLine("Following are populated leftNeighbour" + " pointers in the tree:"); Console.WriteLine("leftNeighbour of " + root.data + " is " + (root.leftNeighbour != null ? root.leftNeighbour.data : -1)); Console.WriteLine("leftNeighbour of " + root.left.data + " is " + (root.left.leftNeighbour != null ? root.left.leftNeighbour.data : -1)); Console.WriteLine("leftNeighbour of " + root.right.data + " is " + (root.right.leftNeighbour != null ? root.right.leftNeighbour.data : -1) ); Console.WriteLine( "leftNeighbour of " + root.left.left.data + " is " + (root.left.left.leftNeighbour != null ? root.left.left.leftNeighbour.data : -1)); } // Driver Code static public void Main () { /* Constructed binary tree is 10 / \ 8 2 / 3 */ GFG.root = new node(10); GFG.root.left = new node(8); GFG.root.right = new node(2); GFG.root.left.left = new node(3); connectNodesUtil(root); }}// This code is contributed by avanitrachhadiya2155 |
Javascript
<script>// Javascript program to connect nodes// at same level using extended// pre-order traversal// Binary tree node, with extra pointer leftNeighbour// to store the neighbour to left nodesclass node{ /* Constructor that allocates a new node with the given data and null left and right pointers. */ constructor(data) { this.data = data; this.left = null; this.right = null; this.leftNeighbour = null; }}// Array to store the recent visited// node at particular level represented// by indiceslet a=new Array(100);// Function to connect nodes using preorder// traversalfunction connectNodes(p,l){ if (p == null) return; // assigning left neighbor p.leftNeighbour = a[l]; // updating value of the recent // node at level a[l] = p; connectNodes(p.left, l + 1); connectNodes(p.right, l + 1);}// Utility function to connect nodes to neighbours// using preorder traversalfunction connectNodesUtil(root){ // Initialize nodes at every level to null for (let i = 0; i < 100; i++) a[i] = new node(-1); // Populates next left pointer in all nodes connectNodes(root, 0); // Let us check the values of next left pointers document.write( "Following are populated leftNeighbour" + " pointers in the tree:<br>"); document.write( "leftNeighbour of " + root.data + " is " + (root.leftNeighbour != null ? root.leftNeighbour.data : -1)+"<br>"); document.write( "leftNeighbour of " + root.left.data + " is " + (root.left.leftNeighbour != null ? root.left.leftNeighbour.data : -1)+"<br>"); document.write( "leftNeighbour of " + root.right.data + " is " + (root.right.leftNeighbour != null ? root.right.leftNeighbour.data : -1) +"<br>"); document.write( "leftNeighbour of " + root.left.left.data + " is " + (root.left.left.leftNeighbour != null ? root.left.left.leftNeighbour.data : -1)+"<br>");}// Driver Code/* Constructed binary tree is 10 / \ 8 2 / 3 */ let root = new node(10); root.left = new node(8); root.right = new node(2); root.left.left = new node(3); connectNodesUtil(root);// This code is contributed by patel2127</script> |
Output:
Following are populated leftNeighbour pointers in the tree: leftNeighbour of 10 is -1 leftNeighbour of 8 is -1 leftNeighbour of 2 is 8 leftNeighbour of 3 is -1
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
