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

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
- We start by initializing a queue and enqueue the root node into it.
- During each iteration, we get the size of the queue, which represents the number of nodes in the current level.
- We use a variable
start
to keep track of the first node in the level. - Within the inner loop, we dequeue a node and enqueue its left and right children if they exist.
- If
size
becomes 0 orstart
is 1, we print the node's data and setstart
to 0. - 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.
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