« Previous Next »

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

« 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.