Posted on by Kalkicode
Code Queue

Print leftmost and rightmost nodes of a binary tree

The problem at hand involves printing the leftmost and rightmost nodes of each level in a binary tree. The leftmost node of a level is the first node encountered while traversing the level from left to right, and the rightmost node is the last node encountered in the same direction. The task is to print these leftmost and rightmost nodes for each level in the tree.

Problem Statement

Given a binary tree, the goal is to print the leftmost and rightmost nodes of each level in separate lines.

Example

Consider the following binary tree:


      1
    /   \
   2     5
  / \   / \
 3   4 6   7
    / \   /
   8   9 10

The output for this tree would be:

1
2 5
3 7
8 10

Idea to Solve

Corner Nodes in Binary Tree

To solve this problem, we can perform a level order traversal of the tree using a queue. While traversing each level, we keep track of the leftmost and rightmost nodes. The first node encountered in the level is the leftmost, and the last node encountered is the rightmost.

Pseudocode

cornerNode(root):
 Create an empty queue
 Enqueue the root into the queue
 
 while queue is not empty:
     Get the current queue size
     Initialize start = 1
     
     while size > 0:
         Dequeue a node from the queue
         Enqueue its left and right children
         
         Decrease size
         If size == 0 or start == 1:
             Print the node's data
             Set start to 0
     
     Print a new line to move to the next level

Algorithm Explanation

  1. We start by initializing a queue and enqueue the root node into it.
  2. During each iteration, we get the size of the queue, which represents the number of nodes in the current level.
  3. We use a variable start to keep track of the first node in the level.
  4. Within the inner loop, we dequeue a node and enqueue its left and right children if they exist.
  5. If size becomes 0 or start is 1, we print the node's data and set start to 0.
  6. After processing all nodes in the current level, we print a new line to move to the next level.

Code Solution

/*
   C Program 
   Print leftmost and rightmost nodes of a binary tree
*/
#include <stdio.h>
#include <stdlib.h>

struct TreeNode
{
	int key;
	struct TreeNode *left;
	struct TreeNode *right;
};
struct BinaryTree
{
	struct TreeNode *root;
};
struct QNode
{
	struct TreeNode *n;
	struct QNode *next;
};
struct MyQueue
{
	int size;
	struct QNode *front;
	struct QNode *rear;
};
struct BinaryTree *makeTree()
{
	struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
	if (tree == NULL)
	{
		printf("\nMemory Overflow, when creating a new BinaryTree\n");
	}
	else
	{
		tree->root = NULL;
	}
	return tree;
}
struct MyQueue *makeQueue()
{
	// Create dynamic node of MyQueue
	struct MyQueue *q = (struct MyQueue *) malloc(sizeof(struct MyQueue));
	if (q == NULL)
	{
		printf("\n Memory Overflow, when creating a new Queue\n");
	}
	else
	{
		q->front = NULL;
		q->rear = NULL;
		q->size = 0;
	}
	return q;
}
int isSize(struct MyQueue *queue)
{
	return queue->size;
}
struct TreeNode *peek(struct MyQueue *q)
{
	if (isSize(q) == 0)
	{
		printf("\n Empty Queue");
		return NULL;
	}
	return q->front->n;
}
// Add new queue node
void enqueue(struct MyQueue *q, struct TreeNode *element)
{
	// Make a new Queue node
	struct QNode *node = (struct QNode *) malloc(sizeof(struct QNode));
	if (node != NULL)
	{
		// Set node values
		node->n = element;
		node->next = NULL;
		if (q->front == NULL)
		{
			q->front = node;
			q->rear = q->front;
		}
		else
		{
			q->rear->next = node;
			q->rear = node;
		}
		q->size++;
	}
	else
	{
		printf("\nMemory Overflow, when creating a new Queue Node\n");
	}
}
// Remove a queue elements
void dequeue(struct MyQueue *q)
{
	if (isSize(q) > 0)
	{
		struct QNode *remove = q->front;
		if (q->front == q->rear)
		{
			q->rear = NULL;
		}
		q->front = q->front->next;
		q->size = q->size - 1;
		remove->n = NULL;
		remove->next = NULL;
		//free node
		free(remove);
		remove = NULL;
	}
}
// Returns a new node of tree
struct TreeNode *newNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		//Set data and pointer values
		node->key = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return node;
}
void cornerNode(struct TreeNode *root)
{
	struct MyQueue *q = makeQueue();
	// Insert first node of queue
	enqueue(q, root);
	int n = 0;
	int start = 0;
	// Define some auxiliary variable
	struct TreeNode *node = NULL;
	struct TreeNode *auxiliary = NULL;
	while (isSize(q) > 0)
	{
		// Get current queue size
		n = isSize(q);
		start = 1;
		while (n > 0)
		{
			node = peek(q);
			// Remove front node of queue 
			dequeue(q);
			if (node->left != NULL)
			{
				enqueue(q, node->left);
			}
			if (node->right != NULL)
			{
				enqueue(q, node->right);
			}
			// Reduce size
			n--;
			if (n == 0 || start == 1)
			{
				// Print first and last node of tree level
				printf("%d ", node->key);
				start = 0;
			}
		}
		// When change level
		printf("\n");
	}
}
int main(int argc, char
	const *argv[])
{
	struct BinaryTree *tree = makeTree();
	/*
	    
	         1
	       /   \
	      2     5
	     / \   / \
	    3   4 6   7
	       / \   /
	      8   9 10 
	    ---------------
	    Binary Tree

	*/
	tree->root = newNode(1);
	tree->root->left = newNode(2);
	tree->root->left->left = newNode(3);
	tree->root->left->right = newNode(4);
	tree->root->left->right->left = newNode(8);
	tree->root->left->right->right = newNode(9);
	tree->root->right = newNode(5);
	tree->root->right->left = newNode(6);
	tree->root->right->right = newNode(7);
	tree->root->right->right->left = newNode(10);
	// Corner Node (1,2,5,3,7,8,10)
	cornerNode(tree->root);
	return 0;
}

Output

1
2 5
3 7
8 10
/*
    Java Program 
    Print leftmost and rightmost nodes of a binary tree
*/
// Binary Tree node
class TreeNode
{
	public int key;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int key)
	{
		// Set node value
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QNode
{
	public TreeNode n;
	public QNode next;
	public QNode(TreeNode n)
	{
		this.n = n;
		this.next = null;
	}
}
//Define custom queue class
class MyQueue
{
	public QNode front;
	public QNode rear;
	public int size;
	public MyQueue()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	// Add a new node at last of queue
	public void enqueue(TreeNode n)
	{
		QNode node = new QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			this.rear.next = node;
		}
		this.size++;
		this.rear = node;
	}
	// Delete front node of queue
	public void dequeue()
	{
		if (this.front != null)
		{
			if (this.rear == this.front)
			{
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
			this.size--;
		}
	}
	public int isSize()
	{
		return this.size;
	}
	public TreeNode peek()
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set root of tree
		this.root = null;
	}
	public void cornerNode()
	{
		MyQueue q = new MyQueue();
		// Insert first node of queue
		q.enqueue(this.root);
		int n = 0;
		boolean start = true;
		// Define some auxiliary variable
		TreeNode node = null;
		TreeNode auxiliary = null;
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			start = true;
			while (n > 0)
			{
				node = q.peek();
				// Remove front node of queue 
				q.dequeue();
				if (node.left != null)
				{
					q.enqueue(node.left);
				}
				if (node.right != null)
				{
					q.enqueue(node.right);
				}
				// Reduce size
				n--;
				if (n == 0 || start == true)
				{
					// Print first and last node of tree level
					System.out.print("  " + node.key);
					start = false;
				}
			}
			// When change level
			System.out.print("\n");
		}
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		    
		         1
		       /   \
		      2     5
		     / \   / \
		    3   4 6   7
		       / \   /
		      8   9 10 
		    ---------------
		    Binary Tree

		*/
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.left.left = new TreeNode(3);
		tree.root.left.right = new TreeNode(4);
		tree.root.left.right.left = new TreeNode(8);
		tree.root.left.right.right = new TreeNode(9);
		tree.root.right = new TreeNode(5);
		tree.root.right.left = new TreeNode(6);
		tree.root.right.right = new TreeNode(7);
		tree.root.right.right.left = new TreeNode(10);
		// Corner Node (1,2,5,3,7,8,10)
		tree.cornerNode();
	}
}

Output

  1
  2  5
  3  7
  8  10
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program 
    Print leftmost and rightmost nodes of a binary tree
*/
// Binary Tree node
class TreeNode
{
	public: 
    int key;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int key)
	{
		// Set node value
		this->key = key;
		this->left = NULL;
		this->right = NULL;
	}
};
// Queue Node
class QNode
{
	public: 
    TreeNode *n;
	QNode *next;
	QNode(TreeNode *n)
	{
		this->n = n;
		this->next = NULL;
	}
};
//Define custom queue class
class MyQueue
{
	public: 
    QNode *front;
	QNode *rear;
	int size;
	MyQueue()
	{
		this->front = NULL;
		this->rear = NULL;
		this->size = 0;
	}
	// Add a new node at last of queue
	void enqueue(TreeNode *n)
	{
		QNode *node = new QNode(n);
		if (this->front == NULL)
		{
			// When first node of queue
			this->front = node;
		}
		else
		{
			// Add node at last position
			this->rear->next = node;
		}
		this->size++;
		this->rear = node;
	}
	// Delete front node of queue
	void dequeue()
	{
		if (this->front != NULL)
		{
			if (this->rear == this->front)
			{
				this->rear = NULL;
				this->front = NULL;
			}
			else
			{
				this->front = this->front->next;
			}
			this->size--;
		}
	}
	int isSize()
	{
		return this->size;
	}
	TreeNode *peek()
	{
		if (this->isSize() == 0)
		{
			return NULL;
		}
		else
		{
			return this->front->n;
		}
	}
};
class BinaryTree
{
	public: 
    TreeNode *root;
	BinaryTree()
	{
		// Set root of tree
		this->root = NULL;
	}
	void cornerNode()
	{
		MyQueue q = MyQueue();
		// Insert first node of queue
		q.enqueue(this->root);
		int n = 0;
		bool start = true;
		// Define some auxiliary variable
		TreeNode *node = NULL;
		TreeNode *auxiliary = NULL;
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			start = true;
			while (n > 0)
			{
				node = q.peek();
				// Remove front node of queue
				q.dequeue();
				if (node->left != NULL)
				{
					q.enqueue(node->left);
				}
				if (node->right != NULL)
				{
					q.enqueue(node->right);
				}
				// Reduce size
				n--;
				if (n == 0 || start == true)
				{
					// Print first and last node of tree level
					cout << "  " << node->key;
					start = false;
				}
			}
			// When change level
			cout << "\n";
		}
	}
};
int main()
{
	BinaryTree tree = BinaryTree();
	/*
	         1
	       /   \
	      2     5
	     / \   / \
	    3   4 6   7
	       / \   /
	      8   9 10 
	    ---------------
	    Binary Tree
	*/
	tree.root = new TreeNode(1);
	tree.root->left = new TreeNode(2);
	tree.root->left->left = new TreeNode(3);
	tree.root->left->right = new TreeNode(4);
	tree.root->left->right->left = new TreeNode(8);
	tree.root->left->right->right = new TreeNode(9);
	tree.root->right = new TreeNode(5);
	tree.root->right->left = new TreeNode(6);
	tree.root->right->right = new TreeNode(7);
	tree.root->right->right->left = new TreeNode(10);
	// Corner Node (1,2,5,3,7,8,10)
	tree.cornerNode();
	return 0;
}

Output

  1
  2  5
  3  7
  8  10
// Include namespace system
using System;
/*
    C# Program 
    Print leftmost and rightmost nodes of a binary tree
*/
// Binary Tree node
public class TreeNode
{
	public int key;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int key)
	{
		// Set node value
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
public class QNode
{
	public TreeNode n;
	public QNode next;
	public QNode(TreeNode n)
	{
		this.n = n;
		this.next = null;
	}
}
//Define custom queue class
public class MyQueue
{
	public QNode front;
	public QNode rear;
	public int size;
	public MyQueue()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	// Add a new node at last of queue
	public void enqueue(TreeNode n)
	{
		QNode node = new QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			this.rear.next = node;
		}
		this.size++;
		this.rear = node;
	}
	// Delete front node of queue
	public void dequeue()
	{
		if (this.front != null)
		{
			if (this.rear == this.front)
			{
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
			this.size--;
		}
	}
	public int isSize()
	{
		return this.size;
	}
	public TreeNode peek()
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set root of tree
		this.root = null;
	}
	public void cornerNode()
	{
		MyQueue q = new MyQueue();
		// Insert first node of queue
		q.enqueue(this.root);
		int n = 0;
		Boolean start = true;
		// Define some auxiliary variable
		TreeNode node = null;
	
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			start = true;
			while (n > 0)
			{
				node = q.peek();
				// Remove front node of queue
				q.dequeue();
				if (node.left != null)
				{
					q.enqueue(node.left);
				}
				if (node.right != null)
				{
					q.enqueue(node.right);
				}
				// Reduce size
				n--;
				if (n == 0 || start == true)
				{
					// Print first and last node of tree level
					Console.Write("  " + node.key);
					start = false;
				}
			}
			// When change level
			Console.Write("\n");
		}
	}
	public static void Main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		         1
		       /   \
		      2     5
		     / \   / \
		    3   4 6   7
		       / \   /
		      8   9 10 
		    ---------------
		    Binary Tree
		*/
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.left.left = new TreeNode(3);
		tree.root.left.right = new TreeNode(4);
		tree.root.left.right.left = new TreeNode(8);
		tree.root.left.right.right = new TreeNode(9);
		tree.root.right = new TreeNode(5);
		tree.root.right.left = new TreeNode(6);
		tree.root.right.right = new TreeNode(7);
		tree.root.right.right.left = new TreeNode(10);
		// Corner Node (1,2,5,3,7,8,10)
		tree.cornerNode();
	}
}

Output

  1
  2  5
  3  7
  8  10
<?php
/*
    Php Program 
    Print leftmost and rightmost nodes of a binary tree
*/
// Binary Tree node
class TreeNode
{
	public $key;
	public $left;
	public $right;

	function __construct($key)
	{
		// Set node value
		$this->key = $key;
		$this->left = null;
		$this->right = null;
	}
}
// Queue Node
class QNode
{
	public $n;
	public $next;

	function __construct($n)
	{
		$this->n = $n;
		$this->next = null;
	}
}
//Define custom queue class
class MyQueue
{
	public $front;
	public $rear;
	public $size;

	function __construct()
	{
		$this->front = null;
		$this->rear = null;
		$this->size = 0;
	}
	// Add a new node at last of queue
	public	function enqueue($n)
	{
		$node = new QNode($n);
		if ($this->front == null)
		{
			// When first node of queue
			$this->front = $node;
		}
		else
		{
			// Add node at last position
			$this->rear->next = $node;
		}
		$this->size++;
		$this->rear = $node;
	}
	// Delete front node of queue
	public	function dequeue()
	{
		if ($this->front != null)
		{
			if ($this->rear == $this->front)
			{
				$this->rear = null;
				$this->front = null;
			}
			else
			{
				$this->front = $this->front->next;
			}
			$this->size--;
		}
	}
	public	function isSize()
	{
		return $this->size;
	}
	public	function peek()
	{
		if ($this->isSize() == 0)
		{
			return null;
		}
		else
		{
			return $this->front->n;
		}
	}
}
class BinaryTree
{
	public $root;

	function __construct()
	{
		// Set root of tree
		$this->root = null;
	}
	public	function cornerNode()
	{
		$q = new MyQueue();
		// Insert first node of queue
		$q->enqueue($this->root);
		$n = 0;
		$start = true;
		// Define some auxiliary variable
		$node = null;
		while ($q->isSize() > 0)
		{
			// Get current queue size
			$n = $q->isSize();
			$start = true;
			while ($n > 0)
			{
				$node = $q->peek();
				// Remove front node of queue
				$q->dequeue();
				if ($node->left != null)
				{
					$q->enqueue($node->left);
				}
				if ($node->right != null)
				{
					$q->enqueue($node->right);
				}
				// Reduce size
				$n--;
				if ($n == 0 || $start == true)
				{
					// Print first and last node of tree level
					echo "  ". $node->key;
					$start = false;
				}
			}
			// When change level
			echo "\n";
		}
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	         1
	       /   \
	      2     5
	     / \   / \
	    3   4 6   7
	       / \   /
	      8   9 10 
	    ---------------
	    Binary Tree
	*/
	$tree->root = new TreeNode(1);
	$tree->root->left = new TreeNode(2);
	$tree->root->left->left = new TreeNode(3);
	$tree->root->left->right = new TreeNode(4);
	$tree->root->left->right->left = new TreeNode(8);
	$tree->root->left->right->right = new TreeNode(9);
	$tree->root->right = new TreeNode(5);
	$tree->root->right->left = new TreeNode(6);
	$tree->root->right->right = new TreeNode(7);
	$tree->root->right->right->left = new TreeNode(10);
	// Corner Node (1,2,5,3,7,8,10)
	$tree->cornerNode();
}
main();

Output

  1
  2  5
  3  7
  8  10
/*
    Node Js Program 
    Print leftmost and rightmost nodes of a binary tree
*/
// Binary Tree node
class TreeNode
{
	constructor(key)
	{
		// Set node value
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QNode
{
	constructor(n)
	{
		this.n = n;
		this.next = null;
	}
}
//Define custom queue class
class MyQueue
{
	constructor()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	// Add a new node at last of queue
	enqueue(n)
	{
		var node = new QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			this.rear.next = node;
		}
		this.size++;
		this.rear = node;
	}
	// Delete front node of queue
	dequeue()
	{
		if (this.front != null)
		{
			if (this.rear == this.front)
			{
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
			this.size--;
		}
	}
	isSize()
	{
		return this.size;
	}
	peek()
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
class BinaryTree
{
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	cornerNode()
	{
		var q = new MyQueue();
		// Insert first node of queue
		q.enqueue(this.root);
		var n = 0;
		var start = true;
		// Define some auxiliary variable
		var node = null;
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			start = true;
			while (n > 0)
			{
				node = q.peek();
				// Remove front node of queue
				q.dequeue();
				if (node.left != null)
				{
					q.enqueue(node.left);
				}
				if (node.right != null)
				{
					q.enqueue(node.right);
				}
				// Reduce size
				n--;
				if (n == 0 || start == true)
				{
					// Print first and last node of tree level
					process.stdout.write("  " + node.key);
					start = false;
				}
			}
			// When change level
			process.stdout.write("\n");
		}
	}
}

function main()
{
	var tree = new BinaryTree();
	/*
	         1
	       /   \
	      2     5
	     / \   / \
	    3   4 6   7
	       / \   /
	      8   9 10 
	    ---------------
	    Binary Tree
	*/
	tree.root = new TreeNode(1);
	tree.root.left = new TreeNode(2);
	tree.root.left.left = new TreeNode(3);
	tree.root.left.right = new TreeNode(4);
	tree.root.left.right.left = new TreeNode(8);
	tree.root.left.right.right = new TreeNode(9);
	tree.root.right = new TreeNode(5);
	tree.root.right.left = new TreeNode(6);
	tree.root.right.right = new TreeNode(7);
	tree.root.right.right.left = new TreeNode(10);
	// Corner Node (1,2,5,3,7,8,10)
	tree.cornerNode();
}
main();

Output

  1
  2  5
  3  7
  8  10
#  Python 3 Program 
#  Print leftmost and rightmost nodes of a binary tree

#  Binary Tree node
class TreeNode :
	
	def __init__(self, key) :
		#  Set node value
		self.key = key
		self.left = None
		self.right = None
	

#  Queue Node
class QNode :
	
	def __init__(self, n) :
		self.n = n
		self.next = None
	

# Define custom queue class
class MyQueue :
	
	def __init__(self) :
		self.front = None
		self.rear = None
		self.size = 0
	
	#  Add a new node at last of queue
	def enqueue(self, n) :
		node = QNode(n)
		if (self.front == None) :
			#  When first node of queue
			self.front = node
		else :
			#  Add node at last position
			self.rear.next = node
		
		self.size += 1
		self.rear = node
	
	#  Delete front node of queue
	def dequeue(self) :
		if (self.front != None) :
			if (self.rear == self.front) :
				self.rear = None
				self.front = None
			else :
				self.front = self.front.next
			
			self.size -= 1
		
	
	def isSize(self) :
		return self.size
	
	def peek(self) :
		if (self.isSize() == 0) :
			return None
		else :
			return self.front.n
		
	

class BinaryTree :
	
	def __init__(self) :
		#  Set root of tree
		self.root = None
	
	def cornerNode(self) :
		q = MyQueue()
		#  Insert first node of queue
		q.enqueue(self.root)
		n = 0
		start = True
		#  Define some auxiliary variable
		node = None
		while (q.isSize() > 0) :
			#  Get current queue size
			n = q.isSize()
			start = True
			while (n > 0) :
				node = q.peek()
				#  Remove front node of queue
				q.dequeue()
				if (node.left != None) :
					q.enqueue(node.left)
				
				if (node.right != None) :
					q.enqueue(node.right)
				
				#  Reduce size
				n -= 1
				if (n == 0 or start == True) :
					#  Print first and last node of tree level
					print("  ", node.key, end = "")
					start = False
				
			
			#  When change level
			print(end = "\n")
		
	

def main() :
	tree = BinaryTree()
	# 
	#          1
	#        /   \
	#       2     5
	#      / \   / \
	#     3   4 6   7
	#        / \   /
	#       8   9 10 
	#     ---------------
	#     Binary Tree
	
	tree.root = TreeNode(1)
	tree.root.left = TreeNode(2)
	tree.root.left.left = TreeNode(3)
	tree.root.left.right = TreeNode(4)
	tree.root.left.right.left = TreeNode(8)
	tree.root.left.right.right = TreeNode(9)
	tree.root.right = TreeNode(5)
	tree.root.right.left = TreeNode(6)
	tree.root.right.right = TreeNode(7)
	tree.root.right.right.left = TreeNode(10)
	#  Corner Node (1,2,5,3,7,8,10)
	tree.cornerNode()

if __name__ == "__main__": main()

Output

   1
   2   5
   3   7
   8   10
#   Ruby Program 
#   Print leftmost and rightmost nodes of a binary tree

#  Binary Tree node
class TreeNode  
	# Define the accessor and reader of class TreeNode  
	attr_reader :key, :left, :right
	attr_accessor :key, :left, :right
 
	
	def initialize(key) 
		#  Set node value
		self.key = key
		self.left = nil
		self.right = nil
	end

end

#  Queue Node
class QNode  
	# Define the accessor and reader of class QNode  
	attr_reader :n, :next
	attr_accessor :n, :next
 
	
	def initialize(n) 
		self.n = n
		self.next = nil
	end

end

# Define custom queue class
class MyQueue  
	# Define the accessor and reader of class MyQueue  
	attr_reader :front, :rear, :size
	attr_accessor :front, :rear, :size
 
	
	def initialize() 
		self.front = nil
		self.rear = nil
		self.size = 0
	end

	#  Add a new node at last of queue
	def enqueue(n) 
		node = QNode.new(n)
		if (self.front == nil) 
			#  When first node of queue
			self.front = node
		else 
			#  Add node at last position
			self.rear.next = node
		end

		self.size += 1
		self.rear = node
	end

	#  Delete front node of queue
	def dequeue() 
		if (self.front != nil) 
			if (self.rear == self.front) 
				self.rear = nil
				self.front = nil
			else 
				self.front = self.front.next
			end

			self.size -= 1
		end

	end

	def isSize() 
		return self.size
	end

	def peek() 
		if (self.isSize() == 0) 
			return nil
		else 
			return self.front.n
		end

	end

end

class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root
	attr_accessor :root
 
	
	def initialize() 
		#  Set root of tree
		self.root = nil
	end

	def cornerNode() 
		q = MyQueue.new()
		#  Insert first node of queue
		q.enqueue(self.root)
		n = 0
		start = true
		#  Define some auxiliary variable
		node = nil
		while (q.isSize() > 0) 
			#  Get current queue size
			n = q.isSize()
			start = true
			while (n > 0) 
				node = q.peek()
				#  Remove front node of queue
				q.dequeue()
				if (node.left != nil) 
					q.enqueue(node.left)
				end

				if (node.right != nil) 
					q.enqueue(node.right)
				end

				#  Reduce size
				n -= 1
				if (n == 0 || start == true) 
					#  Print first and last node of tree level
					print("  ", node.key)
					start = false
				end

			end

			#  When change level
			print("\n")
		end

	end

end

def main() 
	tree = BinaryTree.new()
	# 
	#          1
	#        /   \
	#       2     5
	#      / \   / \
	#     3   4 6   7
	#        / \   /
	#       8   9 10 
	#     ---------------
	#     Binary Tree
	
	tree.root = TreeNode.new(1)
	tree.root.left = TreeNode.new(2)
	tree.root.left.left = TreeNode.new(3)
	tree.root.left.right = TreeNode.new(4)
	tree.root.left.right.left = TreeNode.new(8)
	tree.root.left.right.right = TreeNode.new(9)
	tree.root.right = TreeNode.new(5)
	tree.root.right.left = TreeNode.new(6)
	tree.root.right.right = TreeNode.new(7)
	tree.root.right.right.left = TreeNode.new(10)
	#  Corner Node (1,2,5,3,7,8,10)
	tree.cornerNode()
end

main()

Output

  1
  2  5
  3  7
  8  10
/*
    Scala Program 
    Print leftmost and rightmost nodes of a binary tree
*/
// Binary Tree node
class TreeNode(var key: Int , var left: TreeNode , var right: TreeNode)
{
	def this(key: Int)
	{
		this(key, null, null);
	}
}
// Queue Node
class QNode(var n: TreeNode , var next: QNode)
{
	def this(n: TreeNode)
	{
		this(n, null);
	}
}
//Define custom queue class
class MyQueue(var front: QNode , var rear: QNode , var size: Int)
{
	def this()
	{
		this(null, null, 0);
	}
	// Add a new node at last of queue
	def enqueue(n: TreeNode): Unit = {
		var node: QNode = new QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			this.rear.next = node;
		}
		this.size += 1;
		this.rear = node;
	}
	// Delete front node of queue
	def dequeue(): Unit = {
		if (this.front != null)
		{
			if (this.rear == this.front)
			{
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
			this.size -= 1;
		}
	}
	def isSize(): Int = {
		return this.size;
	}
	def peek(): TreeNode = {
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	def cornerNode(): Unit = {
		var q: MyQueue = new MyQueue();
		// Insert first node of queue
		q.enqueue(this.root);
		var n: Int = 0;
		var start: Boolean = true;
		// Define some auxiliary variable
		var node: TreeNode = null;
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			start = true;
			while (n > 0)
			{
				node = q.peek();
				// Remove front node of queue
				q.dequeue();
				if (node.left != null)
				{
					q.enqueue(node.left);
				}
				if (node.right != null)
				{
					q.enqueue(node.right);
				}
				// Reduce size
				n -= 1;
				if (n == 0 || start == true)
				{
					// Print first and last node of tree level
					print("  " + node.key);
					start = false;
				}
			}
			// When change level
			print("\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
		         1
		       /   \
		      2     5
		     / \   / \
		    3   4 6   7
		       / \   /
		      8   9 10 
		    ---------------
		    Binary Tree
		*/
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.left.left = new TreeNode(3);
		tree.root.left.right = new TreeNode(4);
		tree.root.left.right.left = new TreeNode(8);
		tree.root.left.right.right = new TreeNode(9);
		tree.root.right = new TreeNode(5);
		tree.root.right.left = new TreeNode(6);
		tree.root.right.right = new TreeNode(7);
		tree.root.right.right.left = new TreeNode(10);
		// Corner Node (1,2,5,3,7,8,10)
		tree.cornerNode();
	}
}

Output

  1
  2  5
  3  7
  8  10
/*
    Swift 4 Program 
    Print leftmost and rightmost nodes of a binary tree
*/
// Binary Tree node
class TreeNode
{
	var key: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ key: Int)
	{
		// Set node value
		self.key = key;
		self.left = nil;
		self.right = nil;
	}
}
// Queue Node
class QNode
{
	var n: TreeNode? ;
	var next: QNode? ;
	init(_ n: TreeNode? )
	{
		self.n = n;
		self.next = nil;
	}
}
//Define custom queue class
class MyQueue
{
	var front: QNode? ;
	var rear: QNode? ;
	var size: Int;
	init()
	{
		self.front = nil;
		self.rear = nil;
		self.size = 0;
	}
	// Add a new node at last of queue
	func enqueue(_ n: TreeNode? )
	{
		let node: QNode? = QNode(n);
		if (self.front == nil)
		{
			// When first node of queue
			self.front = node;
		}
		else
		{
			// Add node at last position
			self.rear!.next = node;
		}
		self.size += 1;
		self.rear = node;
	}
	// Delete front node of queue
	func dequeue()
	{
		if (self.front  != nil)
		{
			if (self.rear === self.front)
			{
				self.rear = nil;
				self.front = nil;
			}
			else
			{
				self.front = self.front!.next;
			}
			self.size -= 1;
		}
	}
	func isSize()->Int
	{
		return self.size;
	}
	func peek()->TreeNode?
	{
		if (self.isSize() == 0)
		{
			return nil;
		}
		else
		{
			return self.front!.n;
		}
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		// Set root of tree
		self.root = nil;
	}
	func cornerNode()
	{
		let q: MyQueue = MyQueue();
		// Insert first node of queue
		q.enqueue(self.root);
		var n: Int = 0;
		var start: Bool = true;
		// Define some auxiliary variable
		var node: TreeNode? = nil;
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			start = true;
			while (n > 0)
			{
				node = q.peek();
				// Remove front node of queue
				q.dequeue();
				if (node!.left  != nil)
				{
					q.enqueue(node!.left);
				}
				if (node!.right  != nil)
				{
					q.enqueue(node!.right);
				}
				// Reduce size
				n -= 1;
				if (n == 0 || start == true)
				{
					// Print first and last node of tree level
					print("  ", node!.key, terminator: "");
					start = false;
				}
			}
			// When change level
			print(terminator: "\n");
		}
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
	         1
	       /   \
	      2     5
	     / \   / \
	    3   4 6   7
	       / \   /
	      8   9 10 
	    ---------------
	    Binary Tree
	*/
	tree.root = TreeNode(1);
	tree.root!.left = TreeNode(2);
	tree.root!.left!.left = TreeNode(3);
	tree.root!.left!.right = TreeNode(4);
	tree.root!.left!.right!.left = TreeNode(8);
	tree.root!.left!.right!.right = TreeNode(9);
	tree.root!.right = TreeNode(5);
	tree.root!.right!.left = TreeNode(6);
	tree.root!.right!.right = TreeNode(7);
	tree.root!.right!.right!.left = TreeNode(10);
	// Corner Node (1,2,5,3,7,8,10)
	tree.cornerNode();
}
main();

Output

   1
   2   5
   3   7
   8   10
/*
    Kotlin Program 
    Print leftmost and rightmost nodes of a binary tree
*/
// Binary Tree node
class TreeNode
{
	var key: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(key: Int)
	{
		// Set node value
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QNode
{
	var n: TreeNode ? ;
	var next: QNode ? ;
	constructor(n: TreeNode ? )
	{
		this.n = n;
		this.next = null;
	}
}
//Define custom queue class
class MyQueue
{
	var front: QNode ? ;
	var rear: QNode ? ;
	var size: Int;
	constructor()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	// Add a new node at last of queue
	fun enqueue(n: TreeNode ? ): Unit
	{
		var node: QNode ? = QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			this.rear?.next = node;
		}
		this.size += 1;
		this.rear = node;
	}
	// Delete front node of queue
	fun dequeue(): Unit
	{
		if (this.front != null)
		{
			if (this.rear == this.front)
			{
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front?.next;
			}
			this.size -= 1;
		}
	}
	fun isSize(): Int
	{
		return this.size;
	}
	fun peek(): TreeNode ?
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front?.n;
		}
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	fun cornerNode(): Unit
	{
		var q: MyQueue = MyQueue();
		// Insert first node of queue
		q.enqueue(this.root);
		var n: Int ;
		var start: Boolean ;
		// Define some auxiliary variable
		var node: TreeNode ? ;
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			start = true;
			while (n > 0)
			{
				node = q.peek();
				// Remove front node of queue
				q.dequeue();
				if (node!=null && node.left != null)
				{
					q.enqueue(node.left);
				}
				if (node!=null &&  node.right != null)
				{
					q.enqueue(node.right);
				}
				// Reduce size
				n -= 1;
				if (n == 0 || start == true)
				{
					// Print first and last node of tree level
					print("  " + node!!.key);
					start = false;
				}
			}
			// When change level
			print("\n");
		}
	}
}
fun main(args: Array <String> ): Unit
{
	var tree: BinaryTree = BinaryTree();
	/*
	         1
	       /   \
	      2     5
	     / \   / \
	    3   4 6   7
	       / \   /
	      8   9 10 
	    ---------------
	    Binary Tree
	*/
	tree.root = TreeNode(1);
	tree.root?.left = TreeNode(2);
	tree.root?.left?.left = TreeNode(3);
	tree.root?.left?.right = TreeNode(4);
	tree.root?.left?.right?.left = TreeNode(8);
	tree.root?.left?.right?.right = TreeNode(9);
	tree.root?.right = TreeNode(5);
	tree.root?.right?.left = TreeNode(6);
	tree.root?.right?.right = TreeNode(7);
	tree.root?.right?.right?.left = TreeNode(10);
	// Corner Node (1,2,5,3,7,8,10)
	tree.cornerNode();
}

Output

  1
  2  5
  3  7
  8  10

Resultant Output Explanation

Given the example binary tree, the leftmost and rightmost nodes for each level are printed as described in the output example.

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the level order traversal. The insertion and removal operations in the queue take constant time.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment