Print binary tree levels in ascending order
Given binary tree which include integer values. Our goal is to print level by level node in sorted order. Assume that unique element present in level order.
Here given code implementation process.
import java.util.HashMap;
import java.util.HashSet;
// Java Program
// Print binary tree levels in ascending order
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void levelNodes(HashMap < Integer,
HashSet < Integer >> record,
TreeNode track, int level)
{
if (track != null)
{
if (!record.containsKey(level))
{
record.put(level, new HashSet < Integer > ());
}
record.get(level).add(track.data);
// Visit left subtree
levelNodes(record, track.left, level + 1);
// Visit right subtree
levelNodes(record, track.right, level + 1);
}
}
// Display sorted nodes by level
public void showSortedNode()
{
if (this.root == null)
{
return;
}
HashMap < Integer, HashSet < Integer >> record =
new HashMap < Integer, HashSet < Integer >> ();
this.levelNodes(record, this.root, 1);
// Get number of level
int n = record.size();
for (int i = 1; i <= n; ++i)
{
// Print level nodes
for (int v: record.get(i))
{
System.out.print(" " + v);
}
System.out.print("\n");
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
11 5
/ \ / \
1 3 7 2
/ \ \ \
9 -1 8 4
----------------------
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(5);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(7);
tree.root.right.left.right = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(-1);
tree.showSortedNode();
}
}Output
10
5 11
1 2 3 7
-1 4 8 9// Include header file
#include <iostream>
#include <set>
#include <unordered_map>
using namespace std;
// C++ Program
// Print binary tree levels in ascending order
// Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
void levelNodes(unordered_map < int, set < int > > &record,
TreeNode *track, int level)
{
if (track != NULL)
{
record[level].insert(track->data);
// Visit left subtree
this->levelNodes(record, track->left, level + 1);
// Visit right subtree
this->levelNodes(record, track->right, level + 1);
}
}
// Display sorted nodes by level
void showSortedNode()
{
if (this->root == NULL)
{
return;
}
unordered_map < int, set < int > > record;
this->levelNodes(record, this->root, 1);
// Get number of level
int n = record.size();
for (int i = 1; i <= n; ++i)
{
// Print level nodes
for (auto &v: record[i])
{
cout << " " << v;
}
cout << "\n";
}
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
11 5
/ \ / \
1 3 7 2
/ \ \ \
9 -1 8 4
----------------------
*/
tree->root = new TreeNode(10);
tree->root->left = new TreeNode(11);
tree->root->right = new TreeNode(5);
tree->root->right->right = new TreeNode(2);
tree->root->right->right->right = new TreeNode(4);
tree->root->right->left = new TreeNode(7);
tree->root->right->left->right = new TreeNode(8);
tree->root->left->left = new TreeNode(1);
tree->root->left->right = new TreeNode(3);
tree->root->left->right->left = new TreeNode(9);
tree->root->left->right->right = new TreeNode(-1);
tree->showSortedNode();
return 0;
}Output
10
5 11
1 2 3 7
-1 4 8 9// Include namespace system
using System;
using System.Collections.Generic;
// Csharp Program
// Print binary tree levels in ascending order
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void levelNodes(Dictionary < int, SortedSet < int > > record,
TreeNode track, int level)
{
if (track != null)
{
if (!record.ContainsKey(level))
{
record.Add(level, new SortedSet < int > ());
}
record[level].Add(track.data);
// Visit left subtree
this.levelNodes(record, track.left, level + 1);
// Visit right subtree
this.levelNodes(record, track.right, level + 1);
}
}
// Display sorted nodes by level
public void showSortedNode()
{
if (this.root == null)
{
return;
}
Dictionary < int, SortedSet < int > > record =
new Dictionary < int, SortedSet < int > > ();
this.levelNodes(record, this.root, 1);
// Get number of level
int n = record.Count;
for (int i = 1; i <= n; ++i)
{
// Print level nodes
foreach(int v in record[i])
{
Console.Write(" " + v);
}
Console.Write("\n");
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
11 5
/ \ / \
1 3 7 2
/ \ \ \
9 -1 8 4
----------------------
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(5);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(7);
tree.root.right.left.right = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(-1);
tree.showSortedNode();
}
}Output
10
5 11
1 2 3 7
-1 4 8 9<?php
// Php Program
// Print binary tree levels in ascending order
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function levelNodes(&$record, $track, $level)
{
if ($track != NULL)
{
if (!array_key_exists($level, $record))
{
$record[$level] = array();
}
$record[$level][] = $track->data;
// Visit left subtree
$this->levelNodes($record, $track->left, $level + 1);
// Visit right subtree
$this->levelNodes($record, $track->right, $level + 1);
}
}
// Display sorted nodes by level
public function showSortedNode()
{
if ($this->root == NULL)
{
return;
}
$record = array();
$this->levelNodes($record, $this->root, 1);
// Get number of level
$n = count($record);
for ($i = 1; $i <= $n; ++$i)
{
sort($record[$i]);
// Print level nodes
foreach($record[$i] as $key => $value)
{
echo(" ".$value);
}
echo("\n");
}
}
}
function main()
{
$tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
11 5
/ \ / \
1 3 7 2
/ \ \ \
9 -1 8 4
----------------------
*/
$tree->root = new TreeNode(10);
$tree->root->left = new TreeNode(11);
$tree->root->right = new TreeNode(5);
$tree->root->right->right = new TreeNode(2);
$tree->root->right->right->right = new TreeNode(4);
$tree->root->right->left = new TreeNode(7);
$tree->root->right->left->right = new TreeNode(8);
$tree->root->left->left = new TreeNode(1);
$tree->root->left->right = new TreeNode(3);
$tree->root->left->right->left = new TreeNode(9);
$tree->root->left->right->right = new TreeNode(-1);
$tree->showSortedNode();
}
main();Output
10
5 11
1 2 3 7
-1 4 8 9// Node JS Program
// Print binary tree levels in ascending order
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
levelNodes(record, track, level)
{
if (track != null)
{
if (!record.has(level))
{
record.set(level, []);
}
record.get(level).push(track.data);
// Visit left subtree
this.levelNodes(record, track.left, level + 1);
// Visit right subtree
this.levelNodes(record, track.right, level + 1);
}
}
// Display sorted nodes by level
showSortedNode()
{
if (this.root == null)
{
return;
}
var record = new Map();
this.levelNodes(record, this.root, 1);
// Get number of level
var n = record.size;
for (var i = 1; i <= n; ++i)
{
// Sort level nodes
record.get(i).sort(function(a, b)
{
return a - b;
});
// Print level nodes
record.get(i).forEach(function(value)
{
process.stdout.write(" " + value)
})
process.stdout.write("\n");
}
}
}
function main()
{
var tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
11 5
/ \ / \
1 3 7 2
/ \ \ \
9 -1 8 4
----------------------
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(5);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(7);
tree.root.right.left.right = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(-1);
tree.showSortedNode();
}
main();Output
10
5 11
1 2 3 7
-1 4 8 9# Python 3 Program
# Print binary tree levels in ascending order
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def levelNodes(self, record, track, level) :
if (track != None) :
if (not(level in record.keys())) :
record[level] = []
record.get(level).append(track.data)
# Visit left subtree
self.levelNodes(record, track.left, level + 1)
# Visit right subtree
self.levelNodes(record, track.right, level + 1)
# Display sorted nodes by level
def showSortedNode(self) :
if (self.root == None) :
return
record = dict()
self.levelNodes(record, self.root, 1)
# Get number of level
n = len(record)
i = 1
while (i <= n) :
# sort level node
record.get(i).sort()
for v in record.get(i):
print(" ", v, end = "")
print(end = "\n")
i += 1
def main() :
tree = BinaryTree()
# Binary Tree
# -----------------------
# 10
# / \
# 11 5
# / \ / \
# 1 3 7 2
# / \ \ \
# 9 -1 8 4
# ----------------------
tree.root = TreeNode(10)
tree.root.left = TreeNode(11)
tree.root.right = TreeNode(5)
tree.root.right.right = TreeNode(2)
tree.root.right.right.right = TreeNode(4)
tree.root.right.left = TreeNode(7)
tree.root.right.left.right = TreeNode(8)
tree.root.left.left = TreeNode(1)
tree.root.left.right = TreeNode(3)
tree.root.left.right.left = TreeNode(9)
tree.root.left.right.right = TreeNode(-1)
tree.showSortedNode()
if __name__ == "__main__": main()Output
10
5 11
1 2 3 7
-1 4 8 9require 'set'
# Ruby Program
# Print binary tree levels in ascending order
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
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 levelNodes(record, track, level)
if (track != nil)
if (!record.key?(level))
record[level] = SortedSet.new()
end
record[level].add(track.data)
# Visit left subtree
self.levelNodes(record, track.left, level + 1)
# Visit right subtree
self.levelNodes(record, track.right, level + 1)
end
end
# Display sorted nodes by level
def showSortedNode()
if (self.root == nil)
return
end
record = Hash.new()
self.levelNodes(record, self.root, 1)
# Get number of level
n = record.size()
i = 1
while (i <= n)
# Print level nodes
record[i].each do |num|
print(" ", num)
end
print("\n")
i += 1
end
end
end
def main()
tree = BinaryTree.new()
# Binary Tree
# -----------------------
# 10
# / \
# 11 5
# / \ / \
# 1 3 7 2
# / \ \ \
# 9 -1 8 4
# ----------------------
tree.root = TreeNode.new(10)
tree.root.left = TreeNode.new(11)
tree.root.right = TreeNode.new(5)
tree.root.right.right = TreeNode.new(2)
tree.root.right.right.right = TreeNode.new(4)
tree.root.right.left = TreeNode.new(7)
tree.root.right.left.right = TreeNode.new(8)
tree.root.left.left = TreeNode.new(1)
tree.root.left.right = TreeNode.new(3)
tree.root.left.right.left = TreeNode.new(9)
tree.root.left.right.right = TreeNode.new(-1)
tree.showSortedNode()
end
main()Output
10
5 11
1 2 3 7
-1 4 8 9
import scala.collection.mutable._;
// Scala Program
// Print binary tree levels in ascending order
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def levelNodes(record: HashMap[Int, HashSet[Int]],
track: TreeNode, level: Int): Unit = {
if (track != null)
{
if (!record.contains(level))
{
record += (level -> new HashSet[Int]());
}
record.get(level).get.add(track.data);
// Visit left subtree
levelNodes(record, track.left, level + 1);
// Visit right subtree
levelNodes(record, track.right, level + 1);
}
}
// Display sorted nodes by level
def showSortedNode(): Unit = {
if (this.root == null)
{
return;
}
var record = new HashMap[Int,HashSet[Int]]();
this.levelNodes(record, this.root, 1);
// Get number of level
var n: Int = record.size;
var i: Int = 1;
while (i <= n)
{
// Print level nodes
for (v <- record.get(i).get)
{
print(" " + v);
}
print("\n");
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
11 5
/ \ / \
1 3 7 2
/ \ \ \
9 -1 8 4
----------------------
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(5);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(7);
tree.root.right.left.right = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(-1);
tree.showSortedNode();
}
}Output
10
5 11
1 2 3 7
-1 4 8 9import Foundation;
// Swift 4 Program
// Print binary tree levels in ascending order
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func levelNodes(_ record: inout[Int : Set<Int> ],
_ track: TreeNode? , _ level : Int)
{
if (track != nil)
{
if (!record.keys.contains(level))
{
record[level] = Set<Int>();
}
record[level]!.insert(track!.data);
// Visit left subtree
self.levelNodes(&record, track!.left, level + 1);
// Visit right subtree
self.levelNodes(&record, track!.right, level + 1);
}
}
// Display sorted nodes by level
func showSortedNode()
{
if (self.root == nil)
{
return;
}
var record = [Int : Set<Int> ]();
self.levelNodes(&record, self.root, 1);
// Get number of level
let n: Int = record.count;
var i: Int = 1;
while (i <= n)
{
// Print level nodes
for v in record[i]!.sorted()
{
print(" ", v, terminator: "");
}
print(terminator: "\n");
i += 1;
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
11 5
/ \ / \
1 3 7 2
/ \ \ \
9 -1 8 4
----------------------
*/
tree.root = TreeNode(10);
tree.root!.left = TreeNode(11);
tree.root!.right = TreeNode(5);
tree.root!.right!.right = TreeNode(2);
tree.root!.right!.right!.right = TreeNode(4);
tree.root!.right!.left = TreeNode(7);
tree.root!.right!.left!.right = TreeNode(8);
tree.root!.left!.left = TreeNode(1);
tree.root!.left!.right = TreeNode(3);
tree.root!.left!.right!.left = TreeNode(9);
tree.root!.left!.right!.right = TreeNode(-1);
tree.showSortedNode();
}
main();Output
10
5 11
1 2 3 7
-1 4 8 9// Kotlin Program
// Print binary tree levels in ascending order
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun levelNodes(record: HashMap < Int, HashSet < Int >> ,
track: TreeNode ? , level : Int): Unit
{
if (track != null)
{
if (!record.containsKey(level))
{
record.put(level, hashSetOf <Int> ());
}
record.getValue(level).add(track.data);
// Visit left subtree
this.levelNodes(record, track.left, level + 1);
// Visit right subtree
this.levelNodes(record, track.right, level + 1);
}
}
// Display sorted nodes by level
fun showSortedNode(): Unit
{
if (this.root == null)
{
return;
}
val record = hashMapOf < Int, HashSet < Int >> ();
this.levelNodes(record, this.root, 1);
// Get number of level
val n: Int = record.count();
var i: Int = 1;
while (i <= n)
{
// Print level nodes
for (v in record.getValue(i))
{
print(" " + v);
}
print("\n");
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
11 5
/ \ / \
1 3 7 2
/ \ \ \
9 -1 8 4
----------------------
*/
tree.root = TreeNode(10);
tree.root?.left = TreeNode(11);
tree.root?.right = TreeNode(5);
tree.root?.right?.right = TreeNode(2);
tree.root?.right?.right?.right = TreeNode(4);
tree.root?.right?.left = TreeNode(7);
tree.root?.right?.left?.right = TreeNode(8);
tree.root?.left?.left = TreeNode(1);
tree.root?.left?.right = TreeNode(3);
tree.root?.left?.right?.left = TreeNode(9);
tree.root?.left?.right?.right = TreeNode(-1);
tree.showSortedNode();
}Output
10
5 11
1 2 3 7
-1 4 8 9For practice task, solve this similar problem when level node is similar (duplicates).
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