« Previous Next »

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  30

package 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  30

import 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

« Previous Next »

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.