Print binary search tree in top down level in spiral manner
Here given code implementation process.
import java.util.Vector;
import java.util.HashMap;
// Java program for
// Print binary search tree in top down level in spiral manner
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 BinarySearchTree
{
public TreeNode root;
public BinarySearchTree()
{
this.root = null;
}
public void addNode(int data)
{
TreeNode node = new TreeNode(data);
if (this.root == null)
{
this.root = node;
}
else
{
TreeNode find = this.root;
// Add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
public void findLevelNode(TreeNode node,
HashMap < Integer, Vector < Integer >> record,
int level)
{
if (node != null)
{
if (!record.containsKey(level))
{
record.put(level, new Vector < Integer > ());
}
// Get level node
record.get(level).add(node.data);
findLevelNode(node.left, record, level + 1);
findLevelNode(node.right, record, level + 1);
}
}
public void printLevelLR(HashMap < Integer,
Vector < Integer >> record, int level)
{
for (int i = 0; i < record.get(level).size(); ++i)
{
System.out.print(" " + record.get(level).get(i));
}
System.out.print("\n");
}
public void printLevelRL(HashMap < Integer,
Vector < Integer >> record, int level)
{
for (int i = record.get(level).size() - 1; i >= 0; --i)
{
System.out.print(" " + record.get(level).get(i));
}
System.out.print("\n");
}
public void alternateLevel()
{
if (this.root != null)
{
HashMap < Integer, Vector < Integer >> record =
new HashMap < Integer, Vector < Integer >> ();
findLevelNode(this.root, record, 1);
int i = 1;
int j = record.size();
while (i <= j)
{
if (i != j)
{
// Top level
printLevelLR(record, i);
// Bottom level
printLevelRL(record, j);
i++;
j--;
}
else
{
// Middle level
printLevelLR(record, i);
i++;
}
}
}
}
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/*
70
/ \
/ \
60 80
/ \ / \
30 65 75 90
/ \ / \ \
10 40 73 77 95
*/
tree.addNode(70);
tree.addNode(60);
tree.addNode(30);
tree.addNode(65);
tree.addNode(10);
tree.addNode(40);
tree.addNode(80);
tree.addNode(75);
tree.addNode(73);
tree.addNode(77);
tree.addNode(90);
tree.addNode(95);
tree.alternateLevel();
}
}Output
70
95 77 73 40 10
60 80
90 75 65 30// Include header file
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
// C++ program for
// Print binary search tree in top down level in spiral manner
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 BinarySearchTree
{
public: TreeNode *root;
BinarySearchTree()
{
this->root = NULL;
}
void addNode(int data)
{
TreeNode *node = new TreeNode(data);
if (this->root == NULL)
{
this->root = node;
}
else
{
TreeNode *find = this->root;
// Add new node to proper position
while (find != NULL)
{
if (find->data >= data)
{
if (find->left == NULL)
{
find->left = node;
return;
}
else
{
// Visit left sub-tree
find = find->left;
}
}
else
{
if (find->right == NULL)
{
find->right = node;
return;
}
else
{
// Visit right sub-tree
find = find->right;
}
}
}
}
}
void findLevelNode(TreeNode *node,
unordered_map < int, vector < int > > &record, int level)
{
if (node != NULL)
{
// Get level node
record[level].push_back(node->data);
this->findLevelNode(node->left, record, level + 1);
this->findLevelNode(node->right, record, level + 1);
}
}
void printLevelLR(unordered_map < int, vector < int > > record,
int level)
{
for (int i = 0; i < record[level].size(); ++i)
{
cout << " " << record[level].at(i);
}
cout << "\n";
}
void printLevelRL(unordered_map < int, vector < int > > record,
int level)
{
for (int i = record[level].size() - 1; i >= 0; --i)
{
cout << " " << record[level].at(i);
}
cout << "\n";
}
void alternateLevel()
{
if (this->root != NULL)
{
unordered_map < int, vector < int > > record;
this->findLevelNode(this->root, record, 1);
int i = 1;
int j = record.size();
while (i <= j)
{
if (i != j)
{
// Top level
this->printLevelLR(record, i);
// Bottom level
this->printLevelRL(record, j);
i++;
j--;
}
else
{
// Middle level
this->printLevelLR(record, i);
i++;
}
}
}
}
};
int main()
{
BinarySearchTree *tree = new BinarySearchTree();
/*
70
/ \
/ \
60 80
/ \ / \
30 65 75 90
/ \ / \ \
10 40 73 77 95
*/
tree->addNode(70);
tree->addNode(60);
tree->addNode(30);
tree->addNode(65);
tree->addNode(10);
tree->addNode(40);
tree->addNode(80);
tree->addNode(75);
tree->addNode(73);
tree->addNode(77);
tree->addNode(90);
tree->addNode(95);
tree->alternateLevel();
return 0;
}Output
70
95 77 73 40 10
60 80
90 75 65 30package main
import "fmt"
// Go program for
// Print binary search tree in top down level in spiral manner
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 BinarySearchTree struct {
root * TreeNode
}
func getBinarySearchTree() * BinarySearchTree {
var me *BinarySearchTree = &BinarySearchTree {}
me.root = nil
return me
}
func(this *BinarySearchTree) addNode(data int) {
var node * TreeNode = getTreeNode(data)
if this.root == nil {
this.root = node
} else {
var find * TreeNode = this.root
// Add new node to proper position
for (find != nil) {
if find.data >= data {
if find.left == nil {
find.left = node
return
} else {
// Visit left sub-tree
find = find.left
}
} else {
if find.right == nil {
find.right = node
return
} else {
// Visit right sub-tree
find = find.right
}
}
}
}
}
func(this BinarySearchTree) findLevelNode(node * TreeNode,
record map[int][]int, level int) {
if node != nil {
// Get level node
record[level] = append(record[level], node.data)
this.findLevelNode(node.left, record, level + 1)
this.findLevelNode(node.right, record, level + 1)
}
}
func(this BinarySearchTree) printLevelLR(record map[int][]int, level int) {
for i := 0 ; i < len(record[level]) ; i++ {
fmt.Print(" ", record[level][i])
}
fmt.Print("\n")
}
func(this BinarySearchTree) printLevelRL(record map[int][]int, level int) {
for i := len(record[level]) - 1 ; i >= 0 ; i-- {
fmt.Print(" ", record[level][i])
}
fmt.Print("\n")
}
func(this BinarySearchTree) alternateLevel() {
if this.root != nil {
var record = make(map[int][]int)
this.findLevelNode(this.root, record, 1)
var i int = 1
var j int = len(record)
for (i <= j) {
if i != j {
// Top level
this.printLevelLR(record, i)
// Bottom level
this.printLevelRL(record, j)
i++
j--
} else {
// Middle level
this.printLevelLR(record, i)
i++
}
}
}
}
func main() {
var tree * BinarySearchTree = getBinarySearchTree()
/*
70
/ \
/ \
60 80
/ \ / \
30 65 75 90
/ \ / \ \
10 40 73 77 95
*/
tree.addNode(70)
tree.addNode(60)
tree.addNode(30)
tree.addNode(65)
tree.addNode(10)
tree.addNode(40)
tree.addNode(80)
tree.addNode(75)
tree.addNode(73)
tree.addNode(77)
tree.addNode(90)
tree.addNode(95)
tree.alternateLevel()
}Output
70
95 77 73 40 10
60 80
90 75 65 30// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Print binary search tree in top down level in spiral manner
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 BinarySearchTree
{
public TreeNode root;
public BinarySearchTree()
{
this.root = null;
}
public void addNode(int data)
{
TreeNode node = new TreeNode(data);
if (this.root == null)
{
this.root = node;
}
else
{
TreeNode find = this.root;
// Add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
public void findLevelNode(TreeNode node,
Dictionary < int, List < int >> record,
int level)
{
if (node != null)
{
if (!record.ContainsKey(level))
{
record.Add(level, new List < int > ());
}
// Get level node
record[level].Add(node.data);
this.findLevelNode(node.left, record, level + 1);
this.findLevelNode(node.right, record, level + 1);
}
}
public void printLevelLR(Dictionary < int, List < int >> record,
int level)
{
for (int i = 0; i < record[level].Count; ++i)
{
Console.Write(" " + record[level][i]);
}
Console.Write("\n");
}
public void printLevelRL(Dictionary < int, List < int >> record,
int level)
{
for (int i = record[level].Count - 1; i >= 0; --i)
{
Console.Write(" " + record[level][i]);
}
Console.Write("\n");
}
public void alternateLevel()
{
if (this.root != null)
{
Dictionary < int, List < int >> record =
new Dictionary < int, List < int >> ();
this.findLevelNode(this.root, record, 1);
int i = 1;
int j = record.Count;
while (i <= j)
{
if (i != j)
{
// Top level
this.printLevelLR(record, i);
// Bottom level
this.printLevelRL(record, j);
i++;
j--;
}
else
{
// Middle level
this.printLevelLR(record, i);
i++;
}
}
}
}
public static void Main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/*
70
/ \
/ \
60 80
/ \ / \
30 65 75 90
/ \ / \ \
10 40 73 77 95
*/
tree.addNode(70);
tree.addNode(60);
tree.addNode(30);
tree.addNode(65);
tree.addNode(10);
tree.addNode(40);
tree.addNode(80);
tree.addNode(75);
tree.addNode(73);
tree.addNode(77);
tree.addNode(90);
tree.addNode(95);
tree.alternateLevel();
}
}Output
70
95 77 73 40 10
60 80
90 75 65 30<?php
// Php program for
// Print binary search tree in top down level in spiral manner
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 BinarySearchTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function addNode($data)
{
$node = new TreeNode($data);
if ($this->root == NULL)
{
$this->root = $node;
}
else
{
$find = $this->root;
// Add new node to proper position
while ($find != NULL)
{
if ($find->data >= $data)
{
if ($find->left == NULL)
{
$find->left = $node;
return;
}
else
{
// Visit left sub-tree
$find = $find->left;
}
}
else
{
if ($find->right == NULL)
{
$find->right = $node;
return;
}
else
{
// Visit right sub-tree
$find = $find->right;
}
}
}
}
}
public function findLevelNode($node, &$record, $level)
{
if ($node != NULL)
{
if (!array_key_exists($level, $record))
{
$record[$level] = array();
}
// Get level node
$record[$level][] = $node->data;
$this->findLevelNode($node->left, $record, $level + 1);
$this->findLevelNode($node->right, $record, $level + 1);
}
}
public function printLevelLR($record, $level)
{
for ($i = 0; $i < count($record[$level]); ++$i)
{
echo(" ".$record[$level][$i]);
}
echo("\n");
}
public function printLevelRL($record, $level)
{
for ($i = count($record[$level]) - 1; $i >= 0; --$i)
{
echo(" ".$record[$level][$i]);
}
echo("\n");
}
public function alternateLevel()
{
if ($this->root != NULL)
{
$record = array();
$this->findLevelNode($this->root, $record, 1);
$i = 1;
$j = count($record);
while ($i <= $j)
{
if ($i != $j)
{
// Top level
$this->printLevelLR($record, $i);
// Bottom level
$this->printLevelRL($record, $j);
$i++;
$j--;
}
else
{
// Middle level
$this->printLevelLR($record, $i);
$i++;
}
}
}
}
}
function main()
{
$tree = new BinarySearchTree();
/*
70
/ \
/ \
60 80
/ \ / \
30 65 75 90
/ \ / \ \
10 40 73 77 95
*/
$tree->addNode(70);
$tree->addNode(60);
$tree->addNode(30);
$tree->addNode(65);
$tree->addNode(10);
$tree->addNode(40);
$tree->addNode(80);
$tree->addNode(75);
$tree->addNode(73);
$tree->addNode(77);
$tree->addNode(90);
$tree->addNode(95);
$tree->alternateLevel();
}
main();Output
70
95 77 73 40 10
60 80
90 75 65 30// Node JS program for
// Print binary search tree in top down level in spiral manner
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
constructor()
{
this.root = null;
}
addNode(data)
{
var node = new TreeNode(data);
if (this.root == null)
{
this.root = node;
}
else
{
var find = this.root;
// Add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
findLevelNode(node, record, level)
{
if (node != null)
{
if (!record.has(level))
{
record.set(level, []);
}
// Get level node
record.get(level).push(node.data);
this.findLevelNode(node.left, record, level + 1);
this.findLevelNode(node.right, record, level + 1);
}
}
printLevelLR(record, level)
{
for (var i = 0; i < record.get(level).length; ++i)
{
process.stdout.write(" " + record.get(level)[i]);
}
process.stdout.write("\n");
}
printLevelRL(record, level)
{
for (var i = record.get(level).length - 1; i >= 0; --i)
{
process.stdout.write(" " + record.get(level)[i]);
}
process.stdout.write("\n");
}
alternateLevel()
{
if (this.root != null)
{
var record = new Map();
this.findLevelNode(this.root, record, 1);
var i = 1;
var j = record.size;
while (i <= j)
{
if (i != j)
{
// Top level
this.printLevelLR(record, i);
// Bottom level
this.printLevelRL(record, j);
i++;
j--;
}
else
{
// Middle level
this.printLevelLR(record, i);
i++;
}
}
}
}
}
function main()
{
var tree = new BinarySearchTree();
/*
70
/ \
/ \
60 80
/ \ / \
30 65 75 90
/ \ / \ \
10 40 73 77 95
*/
tree.addNode(70);
tree.addNode(60);
tree.addNode(30);
tree.addNode(65);
tree.addNode(10);
tree.addNode(40);
tree.addNode(80);
tree.addNode(75);
tree.addNode(73);
tree.addNode(77);
tree.addNode(90);
tree.addNode(95);
tree.alternateLevel();
}
main();Output
70
95 77 73 40 10
60 80
90 75 65 30# Python 3 program for
# Print binary search tree in top down level in spiral manner
class TreeNode :
# Data value
# Indicates left and right subtree
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
class BinarySearchTree :
def __init__(self) :
self.root = None
def addNode(self, data) :
node = TreeNode(data)
if (self.root == None) :
self.root = node
else :
find = self.root
# Add new node to proper position
while (find != None) :
if (find.data >= data) :
if (find.left == None) :
find.left = node
return
else :
# Visit left sub-tree
find = find.left
else :
if (find.right == None) :
find.right = node
return
else :
# Visit right sub-tree
find = find.right
def findLevelNode(self, node, record, level) :
if (node != None) :
if (not(level in record.keys())) :
record[level] = []
# Get level node
record.get(level).append(node.data)
self.findLevelNode(node.left, record, level + 1)
self.findLevelNode(node.right, record, level + 1)
def printLevelLR(self, record, level) :
i = 0
while (i < len(record.get(level))) :
print(" ", record.get(level)[i], end = "")
i += 1
print(end = "\n")
def printLevelRL(self, record, level) :
i = len(record.get(level)) - 1
while (i >= 0) :
print(" ", record.get(level)[i], end = "")
i -= 1
print(end = "\n")
def alternateLevel(self) :
if (self.root != None) :
record = dict()
self.findLevelNode(self.root, record, 1)
i = 1
j = len(record)
while (i <= j) :
if (i != j) :
# Top level
self.printLevelLR(record, i)
# Bottom level
self.printLevelRL(record, j)
i += 1
j -= 1
else :
# Middle level
self.printLevelLR(record, i)
i += 1
def main() :
tree = BinarySearchTree()
# 70
# / \
# / \
# 60 80
# / \ / \
# 30 65 75 90
# / \ / \ \
# 10 40 73 77 95
tree.addNode(70)
tree.addNode(60)
tree.addNode(30)
tree.addNode(65)
tree.addNode(10)
tree.addNode(40)
tree.addNode(80)
tree.addNode(75)
tree.addNode(73)
tree.addNode(77)
tree.addNode(90)
tree.addNode(95)
tree.alternateLevel()
if __name__ == "__main__": main()Output
70
95 77 73 40 10
60 80
90 75 65 30# Ruby program for
# Print binary search tree in top down level in spiral manner
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 BinarySearchTree
# Define the accessor and reader of class BinarySearchTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def addNode(data)
node = TreeNode.new(data)
if (self.root == nil)
self.root = node
else
find = self.root
# Add new node to proper position
while (find != nil)
if (find.data >= data)
if (find.left == nil)
find.left = node
return
else
# Visit left sub-tree
find = find.left
end
else
if (find.right == nil)
find.right = node
return
else
# Visit right sub-tree
find = find.right
end
end
end
end
end
def findLevelNode(node, record, level)
if (node != nil)
if (!record.key?(level))
record[level] = []
end
# Get level node
record[level].push(node.data)
self.findLevelNode(node.left, record, level + 1)
self.findLevelNode(node.right, record, level + 1)
end
end
def printLevelLR(record, level)
i = 0
while (i < record[level].length)
print(" ", record[level][i])
i += 1
end
print("\n")
end
def printLevelRL(record, level)
i = record[level].length - 1
while (i >= 0)
print(" ", record[level][i])
i -= 1
end
print("\n")
end
def alternateLevel()
if (self.root != nil)
record = Hash.new()
self.findLevelNode(self.root, record, 1)
i = 1
j = record.size()
while (i <= j)
if (i != j)
# Top level
self.printLevelLR(record, i)
# Bottom level
self.printLevelRL(record, j)
i += 1
j -= 1
else
# Middle level
self.printLevelLR(record, i)
i += 1
end
end
end
end
end
def main()
tree = BinarySearchTree.new()
# 70
# / \
# / \
# 60 80
# / \ / \
# 30 65 75 90
# / \ / \ \
# 10 40 73 77 95
tree.addNode(70)
tree.addNode(60)
tree.addNode(30)
tree.addNode(65)
tree.addNode(10)
tree.addNode(40)
tree.addNode(80)
tree.addNode(75)
tree.addNode(73)
tree.addNode(77)
tree.addNode(90)
tree.addNode(95)
tree.alternateLevel()
end
main()Output
70
95 77 73 40 10
60 80
90 75 65 30
import scala.collection.mutable._;
// Scala program for
// Print binary search tree in top down level in spiral manner
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 BinarySearchTree(var root: TreeNode)
{
def this()
{
this(null);
}
def addNode(data: Int): Unit = {
var node: TreeNode = new TreeNode(data);
if (this.root == null)
{
this.root = node;
}
else
{
var find: TreeNode = this.root;
// Add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
def findLevelNode(node: TreeNode,
record: HashMap[Int, ArrayBuffer[Int]],
level: Int): Unit = {
if (node != null)
{
if (!record.contains(level))
{
record.addOne(level, new ArrayBuffer[Int]());
}
// Get level node
record.get(level).get += node.data;
findLevelNode(node.left, record, level + 1);
findLevelNode(node.right, record, level + 1);
}
}
def printLevelLR(record: HashMap[Int, ArrayBuffer[Int]],
level: Int): Unit = {
var i: Int = 0;
while (i < record.get(level).get.size)
{
print(" " + record.get(level).get(i));
i += 1;
}
print("\n");
}
def printLevelRL(record: HashMap[Int, ArrayBuffer[Int]],
level: Int): Unit = {
var i: Int = record.get(level).get.size - 1;
while (i >= 0)
{
print(" " + record.get(level).get(i));
i -= 1;
}
print("\n");
}
def alternateLevel(): Unit = {
if (this.root != null)
{
var record: HashMap[Int, ArrayBuffer[Int]] = new HashMap[Int, ArrayBuffer[Int]]();
findLevelNode(this.root, record, 1);
var i: Int = 1;
var j: Int = record.size;
while (i <= j)
{
if (i != j)
{
// Top level
printLevelLR(record, i);
// Bottom level
printLevelRL(record, j);
i += 1;
j -= 1;
}
else
{
// Middle level
printLevelLR(record, i);
i += 1;
}
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinarySearchTree = new BinarySearchTree();
/*
70
/ \
/ \
60 80
/ \ / \
30 65 75 90
/ \ / \ \
10 40 73 77 95
*/
tree.addNode(70);
tree.addNode(60);
tree.addNode(30);
tree.addNode(65);
tree.addNode(10);
tree.addNode(40);
tree.addNode(80);
tree.addNode(75);
tree.addNode(73);
tree.addNode(77);
tree.addNode(90);
tree.addNode(95);
tree.alternateLevel();
}
}Output
70
95 77 73 40 10
60 80
90 75 65 30import Foundation;
// Swift 4 program for
// Print binary search tree in top down level in spiral manner
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 BinarySearchTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func addNode(_ data: Int)
{
let node: TreeNode = TreeNode(data);
if (self.root == nil)
{
self.root = node;
}
else
{
var find: TreeNode? = self.root;
// Add new node to proper position
while (find != nil)
{
if (find!.data >= data)
{
if (find!.left == nil)
{
find!.left = node;
return;
}
else
{
// Visit left sub-tree
find = find!.left;
}
}
else
{
if (find!.right == nil)
{
find!.right = node;
return;
}
else
{
// Visit right sub-tree
find = find!.right;
}
}
}
}
}
func findLevelNode(_ node: TreeNode? ,
_ record : inout[Int : [Int] ], _ level: Int)
{
if (node != nil)
{
if (!record.keys.contains(level))
{
record[level] = [Int]();
}
// Get level node
record[level]!.append(node!.data);
self.findLevelNode(node!.left, &record, level + 1);
self.findLevelNode(node!.right, &record, level + 1);
}
}
func printLevelLR(_ record: [Int : [Int] ], _ level: Int)
{
var i: Int = 0;
while (i < record[level]!.count)
{
print(" ", record[level]![i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
func printLevelRL(_ record: [Int : [Int] ], _ level: Int)
{
var i: Int = record[level]!.count - 1;
while (i >= 0)
{
print(" ", record[level]![i], terminator: "");
i -= 1;
}
print(terminator: "\n");
}
func alternateLevel()
{
if (self.root != nil)
{
var record: [Int : [Int]] = [Int : [Int] ]();
self.findLevelNode(self.root, &record, 1);
var i: Int = 1;
var j: Int = record.count;
while (i <= j)
{
if (i != j)
{
// Top level
self.printLevelLR(record, i);
// Bottom level
self.printLevelRL(record, j);
i += 1;
j -= 1;
}
else
{
// Middle level
self.printLevelLR(record, i);
i += 1;
}
}
}
}
}
func main()
{
let tree: BinarySearchTree = BinarySearchTree();
/*
70
/ \
/ \
60 80
/ \ / \
30 65 75 90
/ \ / \ \
10 40 73 77 95
*/
tree.addNode(70);
tree.addNode(60);
tree.addNode(30);
tree.addNode(65);
tree.addNode(10);
tree.addNode(40);
tree.addNode(80);
tree.addNode(75);
tree.addNode(73);
tree.addNode(77);
tree.addNode(90);
tree.addNode(95);
tree.alternateLevel();
}
main();Output
70
95 77 73 40 10
60 80
90 75 65 30// Kotlin program for
// Print binary search tree in top down level in spiral manner
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 BinarySearchTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun addNode(data: Int): Unit
{
val node: TreeNode = TreeNode(data);
if (this.root == null)
{
this.root = node;
}
else
{
var find: TreeNode ? = this.root;
// Add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = node;
return;
}
else
{
// Visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = node;
return;
}
else
{
// Visit right sub-tree
find = find.right;
}
}
}
}
}
fun findLevelNode(node: TreeNode ? ,
record : HashMap < Int, MutableList < Int >> ,
level : Int): Unit
{
if (node != null)
{
if (!record.containsKey(level))
{
record.put(level, mutableListOf < Int > ());
}
// Get level node
record.getValue(level).add(node.data);
this.findLevelNode(node.left, record, level + 1);
this.findLevelNode(node.right, record, level + 1);
}
}
fun printLevelLR(record: HashMap < Int, MutableList < Int >> ,
level : Int): Unit
{
var i: Int = 0;
while (i < record.getValue(level).size)
{
print(" " + record.getValue(level)[i]);
i += 1;
}
print("\n");
}
fun printLevelRL(record: HashMap < Int, MutableList < Int >> ,
level : Int): Unit
{
var i: Int = record.getValue(level).size - 1;
while (i >= 0)
{
print(" " + record.getValue(level)[i]);
i -= 1;
}
print("\n");
}
fun alternateLevel(): Unit
{
if (this.root != null)
{
val record: HashMap < Int, MutableList < Int >> =
HashMap < Int, MutableList < Int >> ();
this.findLevelNode(this.root, record, 1);
var i: Int = 1;
var j: Int = record.count();
while (i <= j)
{
if (i != j)
{
// Top level
this.printLevelLR(record, i);
// Bottom level
this.printLevelRL(record, j);
i += 1;
j -= 1;
}
else
{
// Middle level
this.printLevelLR(record, i);
i += 1;
}
}
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinarySearchTree = BinarySearchTree();
/*
70
/ \
/ \
60 80
/ \ / \
30 65 75 90
/ \ / \ \
10 40 73 77 95
*/
tree.addNode(70);
tree.addNode(60);
tree.addNode(30);
tree.addNode(65);
tree.addNode(10);
tree.addNode(40);
tree.addNode(80);
tree.addNode(75);
tree.addNode(73);
tree.addNode(77);
tree.addNode(90);
tree.addNode(95);
tree.alternateLevel();
}Output
70
95 77 73 40 10
60 80
90 75 65 30
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