Print extreme nodes of each level of Binary Tree in alternate order

Here given code implementation process.
import java.util.HashMap;
// Java program for
// Print extreme nodes of each level of Binary Tree in alternate order
class TreeNode
{
// Data value
public int data;
// Indicates left and right subtree
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
public void findExtremeNode(TreeNode node,
HashMap < Integer, Integer > record,
int level)
{
if (node != null)
{
if (!record.containsKey(level))
{
// Collect first node of level
record.put(level, node.data);
}
else if (level % 2 == 0)
{
// Update first node of level
record.put(level, node.data);
}
// Visit left subtree
findExtremeNode(node.left, record, level + 1);
// Visit right subtree
findExtremeNode(node.right, record, level + 1);
}
}
public void extremeNode()
{
if (this.root != null)
{
HashMap < Integer, Integer > record =
new HashMap < Integer, Integer > ();
findExtremeNode(this.root, record, 1);
int i = 1;
int n = record.size();
// Display extreme nodes
while (i <= n)
{
System.out.print(" " + record.get(i));
i++;
}
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/* Binary Tree
-----------
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
/ \ \
17 30 10
*/
// Binary tree nodes
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(9);
tree.root.right.left = new TreeNode(5);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(8);
tree.root.left.left.right.left = new TreeNode(17);
tree.root.left.left.right.right = new TreeNode(30);
tree.root.right.right.left.right = new TreeNode(10);
/*
Extreme node of alternate level
-----------
→ 1
/ \
2 3 ←
/ / \
→ 4 5 6
\ / \
7 8 9 ←
/ \ \
→ 17 30 10
*/
tree.extremeNode();
}
}
Output
1 3 4 9 17
// Include header file
#include <iostream>
#include <unordered_map>
using namespace std;
// C++ program for
// Print extreme nodes of each level of Binary Tree in alternate order
class TreeNode
{
public:
// Data value
int data;
// Indicates left and right subtree
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
void findExtremeNode(TreeNode *node,
unordered_map < int, int > &record,
int level)
{
if (node != NULL)
{
if (record.find(level) == record.end())
{
// Collect first node of level
record[level] = node->data;
}
else if (level % 2 == 0)
{
// Update first node of level
record[level] = node->data;
}
// Visit left subtree
this->findExtremeNode(node->left, record, level + 1);
// Visit right subtree
this->findExtremeNode(node->right, record, level + 1);
}
}
void extremeNode()
{
if (this->root != NULL)
{
unordered_map < int, int > record;
this->findExtremeNode(this->root, record, 1);
int i = 1;
int n = record.size();
// Display extreme nodes
while (i <= n)
{
cout << " " << record[i];
i++;
}
}
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*Binary Tree
-----------
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
/ \ \
17 30 10
*/
// Binary tree nodes
tree->root = new TreeNode(1);
tree->root->left = new TreeNode(2);
tree->root->right = new TreeNode(3);
tree->root->right->right = new TreeNode(6);
tree->root->right->right->right = new TreeNode(9);
tree->root->right->left = new TreeNode(5);
tree->root->left->left = new TreeNode(4);
tree->root->left->left->right = new TreeNode(7);
tree->root->right->right->left = new TreeNode(8);
tree->root->left->left->right->left = new TreeNode(17);
tree->root->left->left->right->right = new TreeNode(30);
tree->root->right->right->left->right = new TreeNode(10);
/*
Extreme node of alternate level
-----------
→ 1
/ \
2 3 ←
/ / \
→ 4 5 6
\ / \
7 8 9 ←
/ \ \
→ 17 30 10
*/
tree->extremeNode();
return 0;
}
Output
1 3 4 9 17
package main
import "fmt"
// Go program for
// Print extreme nodes of each level of Binary Tree in alternate order
type TreeNode struct {
// Data value
data int
// Indicates left and right subtree
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
me.data = data
me.left = nil
me.right = nil
return me
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
me.root = nil
return me
}
func(this BinaryTree) findExtremeNode(node * TreeNode,
record map[int]int, level int) {
if node != nil {
if _, found := record[level] ; !found {
// Collect first node of level
record[level] = node.data
} else if level % 2 == 0 {
// Update first node of level
record[level] = node.data
}
// Visit left subtree
this.findExtremeNode(node.left, record, level + 1)
// Visit right subtree
this.findExtremeNode(node.right, record, level + 1)
}
}
func(this BinaryTree) extremeNode() {
if this.root != nil {
var record = make(map[int] int)
this.findExtremeNode(this.root, record, 1)
var i int = 1
var n int = len(record)
// Display extreme nodes
for (i <= n) {
fmt.Print(" ", record[i])
i++
}
}
}
func main() {
var tree * BinaryTree = getBinaryTree()
/* Binary Tree
-----------
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
/ \ \
17 30 10
*/
// Binary tree nodes
tree.root = getTreeNode(1)
tree.root.left = getTreeNode(2)
tree.root.right = getTreeNode(3)
tree.root.right.right = getTreeNode(6)
tree.root.right.right.right = getTreeNode(9)
tree.root.right.left = getTreeNode(5)
tree.root.left.left = getTreeNode(4)
tree.root.left.left.right = getTreeNode(7)
tree.root.right.right.left = getTreeNode(8)
tree.root.left.left.right.left = getTreeNode(17)
tree.root.left.left.right.right = getTreeNode(30)
tree.root.right.right.left.right = getTreeNode(10)
/*
Extreme node of alternate level
-----------
→ 1
/ \
2 3 ←
/ / \
→ 4 5 6
\ / \
7 8 9 ←
/ \ \
→ 17 30 10
*/
tree.extremeNode()
}
Output
1 3 4 9 17
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Print extreme nodes of each level of Binary Tree in alternate order
public class TreeNode
{
// Data value
public int data;
// Indicates left and right subtree
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
public void findExtremeNode(TreeNode node,
Dictionary < int, int > record,
int level)
{
if (node != null)
{
if (!record.ContainsKey(level))
{
// Collect first node of level
record.Add(level, node.data);
}
else if (level % 2 == 0)
{
// Update first node of level
record[level] = node.data;
}
// Visit left subtree
this.findExtremeNode(node.left, record, level + 1);
// Visit right subtree
this.findExtremeNode(node.right, record, level + 1);
}
}
public void extremeNode()
{
if (this.root != null)
{
Dictionary < int, int > record =
new Dictionary < int, int > ();
this.findExtremeNode(this.root, record, 1);
int i = 1;
int n = record.Count;
// Display extreme nodes
while (i <= n)
{
Console.Write(" " + record[i]);
i++;
}
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/* Binary Tree
-----------
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
/ \ \
17 30 10
*/
// Binary tree nodes
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(9);
tree.root.right.left = new TreeNode(5);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(8);
tree.root.left.left.right.left = new TreeNode(17);
tree.root.left.left.right.right = new TreeNode(30);
tree.root.right.right.left.right = new TreeNode(10);
/*
Extreme node of alternate level
-----------
→ 1
/ \
2 3 ←
/ / \
→ 4 5 6
\ / \
7 8 9 ←
/ \ \
→ 17 30 10
*/
tree.extremeNode();
}
}
Output
1 3 4 9 17
<?php
// Php program for
// Print extreme nodes of each level of Binary Tree in alternate order
class TreeNode
{
// Data value
public $data;
// Indicates left and right subtree
public $left;
public $right;
public function __construct($data)
{
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function findExtremeNode($node, &$record, $level)
{
if ($node != NULL)
{
if (!array_key_exists($level, $record))
{
// Collect first node of level
$record[$level] = $node->data;
}
else if ($level % 2 == 0)
{
// Update first node of level
$record[$level] = $node->data;
}
// Visit left subtree
$this->findExtremeNode($node->left, $record, $level + 1);
// Visit right subtree
$this->findExtremeNode($node->right, $record, $level + 1);
}
}
public function extremeNode()
{
if ($this->root != NULL)
{
$record = array();
$this->findExtremeNode($this->root, $record, 1);
$i = 1;
$n = count($record);
// Display extreme nodes
while ($i <= $n)
{
echo(" ".$record[$i]);
$i++;
}
}
}
}
function main()
{
$tree = new BinaryTree();
/* Binary Tree
-----------
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
/ \ \
17 30 10
*/
// Binary tree nodes
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(3);
$tree->root->right->right = new TreeNode(6);
$tree->root->right->right->right = new TreeNode(9);
$tree->root->right->left = new TreeNode(5);
$tree->root->left->left = new TreeNode(4);
$tree->root->left->left->right = new TreeNode(7);
$tree->root->right->right->left = new TreeNode(8);
$tree->root->left->left->right->left = new TreeNode(17);
$tree->root->left->left->right->right = new TreeNode(30);
$tree->root->right->right->left->right = new TreeNode(10);
/*
Extreme node of alternate level
-----------
→ 1
/ \
2 3 ←
/ / \
→ 4 5 6
\ / \
7 8 9 ←
/ \ \
→ 17 30 10
*/
$tree->extremeNode();
}
main();
Output
1 3 4 9 17
// Node JS program for
// Print extreme nodes of each level of Binary Tree in alternate order
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
findExtremeNode(node, record, level)
{
if (node != null)
{
if (!record.has(level))
{
// Collect first node of level
record.set(level, node.data);
}
else if (level % 2 == 0)
{
// Update first node of level
record.set(level, node.data);
}
// Visit left subtree
this.findExtremeNode(node.left, record, level + 1);
// Visit right subtree
this.findExtremeNode(node.right, record, level + 1);
}
}
extremeNode()
{
if (this.root != null)
{
var record = new Map();
this.findExtremeNode(this.root, record, 1);
var i = 1;
var n = record.size;
// Display extreme nodes
while (i <= n)
{
process.stdout.write(" " + record.get(i));
i++;
}
}
}
}
function main()
{
var tree = new BinaryTree();
/* Binary Tree
-----------
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
/ \ \
17 30 10
*/
// Binary tree nodes
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(9);
tree.root.right.left = new TreeNode(5);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(8);
tree.root.left.left.right.left = new TreeNode(17);
tree.root.left.left.right.right = new TreeNode(30);
tree.root.right.right.left.right = new TreeNode(10);
/*
Extreme node of alternate level
-----------
→ 1
/ \
2 3 ←
/ / \
→ 4 5 6
\ / \
7 8 9 ←
/ \ \
→ 17 30 10
*/
tree.extremeNode();
}
main();
Output
1 3 4 9 17
# Python 3 program for
# Print extreme nodes of each level of Binary Tree in alternate order
class TreeNode :
# Data value
# Indicates left and right subtree
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def findExtremeNode(self, node, record, level) :
if (node != None) :
if (not(level in record.keys())) :
# Collect first node of level
record[level] = node.data
elif (level % 2 == 0) :
# Update first node of level
record[level] = node.data
# Visit left subtree
self.findExtremeNode(node.left, record, level + 1)
# Visit right subtree
self.findExtremeNode(node.right, record, level + 1)
def extremeNode(self) :
if (self.root != None) :
record = dict()
self.findExtremeNode(self.root, record, 1)
i = 1
n = len(record)
# Display extreme nodes
while (i <= n) :
print(" ", record.get(i), end = "")
i += 1
def main() :
tree = BinaryTree()
# Binary Tree
# -----------
# 1
# / \
# 2 3
# / / \
# 4 5 6
# \ / \
# 7 8 9
# / \ \
# 17 30 10
# Binary tree nodes
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.right.right = TreeNode(6)
tree.root.right.right.right = TreeNode(9)
tree.root.right.left = TreeNode(5)
tree.root.left.left = TreeNode(4)
tree.root.left.left.right = TreeNode(7)
tree.root.right.right.left = TreeNode(8)
tree.root.left.left.right.left = TreeNode(17)
tree.root.left.left.right.right = TreeNode(30)
tree.root.right.right.left.right = TreeNode(10)
# Extreme node of alternate level
# -----------
# → 1
# / \
# 2 3 ←
# / / \
# → 4 5 6
# \ / \
# 7 8 9 ←
# / \ \
# → 17 30 10
tree.extremeNode()
if __name__ == "__main__": main()
Output
1 3 4 9 17
# Ruby program for
# Print extreme nodes of each level of Binary Tree in alternate order
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
# Data value
# Indicates left and right subtree
def initialize(data)
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def findExtremeNode(node, record, level)
if (node != nil)
if (!record.key?(level))
# Collect first node of level
record[level] = node.data
elsif (level % 2 == 0)
# Update first node of level
record[level] = node.data
end
# Visit left subtree
self.findExtremeNode(node.left, record, level + 1)
# Visit right subtree
self.findExtremeNode(node.right, record, level + 1)
end
end
def extremeNode()
if (self.root != nil)
record = Hash.new()
self.findExtremeNode(self.root, record, 1)
i = 1
n = record.size()
# Display extreme nodes
while (i <= n)
print(" ", record[i])
i += 1
end
end
end
end
def main()
tree = BinaryTree.new()
# Binary Tree
# -----------
# 1
# / \
# 2 3
# / / \
# 4 5 6
# \ / \
# 7 8 9
# / \ \
# 17 30 10
# Binary tree nodes
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(3)
tree.root.right.right = TreeNode.new(6)
tree.root.right.right.right = TreeNode.new(9)
tree.root.right.left = TreeNode.new(5)
tree.root.left.left = TreeNode.new(4)
tree.root.left.left.right = TreeNode.new(7)
tree.root.right.right.left = TreeNode.new(8)
tree.root.left.left.right.left = TreeNode.new(17)
tree.root.left.left.right.right = TreeNode.new(30)
tree.root.right.right.left.right = TreeNode.new(10)
# Extreme node of alternate level
# -----------
# → 1
# / \
# 2 3 ←
# / / \
# → 4 5 6
# \ / \
# 7 8 9 ←
# / \ \
# → 17 30 10
tree.extremeNode()
end
main()
Output
1 3 4 9 17
import scala.collection.mutable._;
// Scala program for
// Print extreme nodes of each level of Binary Tree in alternate order
class TreeNode(
// Data value
var data: Int,
// Indicates left and right subtree
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def findExtremeNode(node: TreeNode,
record: HashMap[Int, Int],
level: Int): Unit = {
if (node != null)
{
if (!record.contains(level))
{
// Collect first node of level
record.addOne(level, node.data);
}
else if (level % 2 == 0)
{
// Update first node of level
record.addOne(level, node.data);
}
// Visit left subtree
findExtremeNode(node.left, record, level + 1);
// Visit right subtree
findExtremeNode(node.right, record, level + 1);
}
}
def extremeNode(): Unit = {
if (this.root != null)
{
var record: HashMap[Int, Int] = new HashMap[Int, Int]();
findExtremeNode(this.root, record, 1);
var i: Int = 1;
var n: Int = record.size;
// Display extreme nodes
while (i <= n)
{
print(" " + record.get(i).get);
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/* Binary Tree
-----------
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
/ \ \
17 30 10
*/
// Binary tree nodes
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(9);
tree.root.right.left = new TreeNode(5);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(8);
tree.root.left.left.right.left = new TreeNode(17);
tree.root.left.left.right.right = new TreeNode(30);
tree.root.right.right.left.right = new TreeNode(10);
/*
Extreme node of alternate level
-----------
→ 1
/ \
2 3 ←
/ / \
→ 4 5 6
\ / \
7 8 9 ←
/ \ \
→ 17 30 10
*/
tree.extremeNode();
}
}
Output
1 3 4 9 17
import Foundation;
// Swift 4 program for
// Print extreme nodes of each level of Binary Tree in alternate order
class TreeNode
{
// Data value
var data: Int;
// Indicates left and right subtree
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func findExtremeNode(_ node: TreeNode? ,
_ record : inout[Int : Int], _ level: Int)
{
if (node != nil)
{
if (!record.keys.contains(level))
{
// Collect first node of level
record[level] = node!.data;
}
else if (level % 2 == 0)
{
// Update first node of level
record[level] = node!.data;
}
// Visit left subtree
self.findExtremeNode(node!.left, &record, level + 1);
// Visit right subtree
self.findExtremeNode(node!.right, &record, level + 1);
}
}
func extremeNode()
{
if (self.root != nil)
{
var record: [Int : Int] = [Int : Int]();
self.findExtremeNode(self.root, &record, 1);
var i: Int = 1;
let n: Int = record.count;
// Display extreme nodes
while (i <= n)
{
print(" ", record[i]!, terminator: "");
i += 1;
}
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/* Binary Tree
-----------
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
/ \ \
17 30 10
*/
// Binary tree nodes
tree.root = TreeNode(1);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(3);
tree.root!.right!.right = TreeNode(6);
tree.root!.right!.right!.right = TreeNode(9);
tree.root!.right!.left = TreeNode(5);
tree.root!.left!.left = TreeNode(4);
tree.root!.left!.left!.right = TreeNode(7);
tree.root!.right!.right!.left = TreeNode(8);
tree.root!.left!.left!.right!.left = TreeNode(17);
tree.root!.left!.left!.right!.right = TreeNode(30);
tree.root!.right!.right!.left!.right = TreeNode(10);
/*
Extreme node of alternate level
-----------
→ 1
/ \
2 3 ←
/ / \
→ 4 5 6
\ / \
7 8 9 ←
/ \ \
→ 17 30 10
*/
tree.extremeNode();
}
main();
Output
1 3 4 9 17
// Kotlin program for
// Print extreme nodes of each level of Binary Tree in alternate order
class TreeNode
{
// Data value
var data: Int;
// Indicates left and right subtree
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun findExtremeNode(node: TreeNode ? ,
record : HashMap < Int, Int > , level : Int): Unit
{
if (node != null)
{
if (!record.containsKey(level))
{
// Collect first node of level
record.put(level, node.data);
}
else if (level % 2 == 0)
{
// Update first node of level
record.put(level, node.data);
}
// Visit left subtree
this.findExtremeNode(node.left, record, level + 1);
// Visit right subtree
this.findExtremeNode(node.right, record, level + 1);
}
}
fun extremeNode(): Unit
{
if (this.root != null)
{
val record: HashMap < Int, Int > = HashMap < Int, Int > ();
this.findExtremeNode(this.root, record, 1);
var i: Int = 1;
val n: Int = record.count();
// Display extreme nodes
while (i <= n)
{
print(" " + record.getValue(i));
i += 1;
}
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/* Binary Tree
-----------
1
/ \
2 3
/ / \
4 5 6
\ / \
7 8 9
/ \ \
17 30 10
*/
// Binary tree nodes
tree.root = TreeNode(1);
tree.root?.left = TreeNode(2);
tree.root?.right = TreeNode(3);
tree.root?.right?.right = TreeNode(6);
tree.root?.right?.right?.right = TreeNode(9);
tree.root?.right?.left = TreeNode(5);
tree.root?.left?.left = TreeNode(4);
tree.root?.left?.left?.right = TreeNode(7);
tree.root?.right?.right?.left = TreeNode(8);
tree.root?.left?.left?.right?.left = TreeNode(17);
tree.root?.left?.left?.right?.right = TreeNode(30);
tree.root?.right?.right?.left?.right = TreeNode(10);
/*
Extreme node of alternate level
-----------
→ 1
/ \
2 3 ←
/ / \
→ 4 5 6
\ / \
7 8 9 ←
/ \ \
→ 17 30 10
*/
tree.extremeNode();
}
Output
1 3 4 9 17
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