Print the boundary nodes in each level of the binary tree

Boundary nodes in each level of bt

First and last node of tree is indicate boundary node of each level. In a binary tree find and display those node. Here given code implementation process.

import java.util.HashMap;
// Java program for
// Print the boundary nodes in each level of the binary tree
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;
	}
}
class Result
{
	public TreeNode first;
	public TreeNode last;
	public Result()
	{
		this.first = null;
		this.last = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	public void findBoundaryNode(TreeNode node, 
                                  HashMap < Integer, Result > record, 
                                  int level)
	{
		if (node != null)
		{
			if (!record.containsKey(level))
			{
				record.put(level, new Result());
			}
			if (record.get(level).first == null)
			{
				// Collect first node
				record.get(level).first = node;
			}
			else
			{
				// Collect last node
				record.get(level).last = node;
			}
          	// Visit left subtree
			findBoundaryNode(node.left, record, level + 1);
          	// Visit right subtree
			findBoundaryNode(node.right, record, level + 1);
		}
	}
	public void findBoundaryLevelNode()
	{
		if (this.root == null)
		{
			return;
		}
		HashMap < Integer, Result > record = 
          new HashMap < Integer, Result > ();
		this.findBoundaryNode(this.root, record, 0);
		int level = 0;
		// Display boundary level node
		while (level < record.size())
		{
			if (record.get(level).first != null)
			{
				// Display first node of level
				System.out.print(record.get(level).first.data);
			}
			if (record.get(level).last != null)
			{
				// Display last node of level
				System.out.print("  " + record.get(level).last.data);
			}
			System.out.print("\n");
			// Change level
			level++;
		}
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*  Binary Tree
		    -----------------------
		          1
		         /  \
		        11   3
		       /    /  \
		      4    5    6   
		     / \    \    \  
		    8   7    12   -4
		       / \    \  
		     -2   9    13
		*/
		// Add Binary tree nodes
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(11);
		tree.root.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(6);
		tree.root.right.right.right = new TreeNode(-4);
		tree.root.right.left = new TreeNode(5);
		tree.root.left.left = new TreeNode(4);
		tree.root.left.left.left = new TreeNode(8);
		tree.root.left.left.right = new TreeNode(7);
		tree.root.left.left.right.left = new TreeNode(-2);
		tree.root.left.left.right.right = new TreeNode(9);
		tree.root.right.left.right = new TreeNode(12);
		tree.root.right.left.right.right = new TreeNode(13);
		/*
                  ↓
                  1 
                 /  \
              → 11   3  ←
               /    /  \
            → 4    5    6  ← 
             / \    \    \  
          → 8   7    12   -4  ←
               / \    \    
           → -2   9    13 ←
    
            --------------------
            Boundary Nodes
        */
		tree.findBoundaryLevelNode();
	}
}

Output

1
11  3
4  6
8  -4
-2  13
// Include header file
#include <iostream>
#include <unordered_map>

using namespace std;
// C++ program for
// Print the boundary nodes in each level of the binary tree
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 Result
{
    public: TreeNode *first;
    TreeNode *last;
    Result()
    {
        this->first = NULL;
        this->last = NULL;
    }
};
class BinaryTree
{
    public: TreeNode *root;
    BinaryTree()
    {
        this->root = NULL;
    }
    void findBoundaryNode(TreeNode *node, 
                          unordered_map < int, Result *> &record, int level)
    {
        if (node != NULL)
        {
            if (record.find(level) == record.end())
            {
                record[level] = new Result();
            }
            if (record[level]->first == NULL)
            {
                // Collect first node
                record[level]->first = node;
            }
            else
            {
                // Collect last node
                record[level]->last = node;
            }
            // Visit left subtree
            this->findBoundaryNode(node->left, record, level + 1);
            // Visit right subtree
            this->findBoundaryNode(node->right, record, level + 1);
        }
    }
    void findBoundaryLevelNode()
    {
        if (this->root == NULL)
        {
            return;
        }
        unordered_map < int, Result *> record;
        this->findBoundaryNode(this->root, record, 0);
        int level = 0;
        // Display boundary level node
        while (level < record.size())
        {
            if (record[level]->first != NULL)
            {
                // Display first node of level
                cout << record[level]->first->data;
            }
            if (record[level]->last != NULL)
            {
                // Display last node of level
                cout << "  " << record[level]->last->data;
            }
            cout << "\n";
            // Change level
            level++;
        }
    }
};
int main()
{
    BinaryTree *tree = new BinaryTree();
    /*Binary Tree
                -----------------------
                      1
                     /  \
                    11   3
                   /    /  \
                  4    5    6   
                 / \    \    \  
                8   7    12   -4
                   / \    \  
                 -2   9    13
            */
    // Add Binary tree nodes
    tree->root = new TreeNode(1);
    tree->root->left = new TreeNode(11);
    tree->root->right = new TreeNode(3);
    tree->root->right->right = new TreeNode(6);
    tree->root->right->right->right = new TreeNode(-4);
    tree->root->right->left = new TreeNode(5);
    tree->root->left->left = new TreeNode(4);
    tree->root->left->left->left = new TreeNode(8);
    tree->root->left->left->right = new TreeNode(7);
    tree->root->left->left->right->left = new TreeNode(-2);
    tree->root->left->left->right->right = new TreeNode(9);
    tree->root->right->left->right = new TreeNode(12);
    tree->root->right->left->right->right = new TreeNode(13);
    /*
              ↓
              1 
             /  \
          → 11   3  ←
           /    /  \
        → 4    5    6  ← 
         / \    \    \  
      → 8   7    12   -4  ←
           / \    \    
       → -2   9    13 ←

        --------------------
        Boundary Nodes
    */
    tree->findBoundaryLevelNode();
    return 0;
}

Output

1
11  3
4  6
8  -4
-2  13
package main
import "fmt"
// Go program for
// Print the boundary nodes in each level of the binary tree
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 Result struct {
	first * TreeNode
	last * TreeNode
}
func getResult() * Result {
	var me *Result = &Result {}
	me.first = nil
	me.last = nil
	return me
}
type BinaryTree struct {
	root * TreeNode
}
func getBinaryTree() * BinaryTree {
	var me *BinaryTree = &BinaryTree {}
	me.root = nil
	return me
}
func(this *BinaryTree) findBoundaryNode(node * TreeNode, record map[int] *Result, level int) {
	if node != nil {
		if _, found := record[level] ; !found {
			record[level] = getResult()
		}
		if record[level].first == nil {
			// Collect first node
			record[level].first = node
		} else {
			// Collect last node
			record[level].last = node
		}
		// Visit left subtree
		this.findBoundaryNode(node.left, record, level + 1)
		// Visit right subtree
		this.findBoundaryNode(node.right, record, level + 1)
	}
}
func(this BinaryTree) findBoundaryLevelNode() {
	if this.root == nil {
		return
	}
	var record = make(map[int] *Result)
	this.findBoundaryNode(this.root, record, 0)
	var level int = 0
	// Display boundary level node
	for (level < len(record)) {
		if record[level].first != nil {
			// Display first node of level
			fmt.Print(record[level].first.data)
		}
		if record[level].last != nil {
			// Display last node of level
			fmt.Print("  ", record[level].last.data)
		}
		fmt.Print("\n")
		// Change level
		level++
	}
}
func main() {
	var tree * BinaryTree = getBinaryTree()
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        11   3
	       /    /  \
	      4    5    6   
	     / \    \    \  
	    8   7    12   -4
	       / \    \  
	     -2   9    13
	*/
	// Add Binary tree nodes
	tree.root = getTreeNode(1)
	tree.root.left = getTreeNode(11)
	tree.root.right = getTreeNode(3)
	tree.root.right.right = getTreeNode(6)
	tree.root.right.right.right = getTreeNode(-4)
	tree.root.right.left = getTreeNode(5)
	tree.root.left.left = getTreeNode(4)
	tree.root.left.left.left = getTreeNode(8)
	tree.root.left.left.right = getTreeNode(7)
	tree.root.left.left.right.left = getTreeNode(-2)
	tree.root.left.left.right.right = getTreeNode(9)
	tree.root.right.left.right = getTreeNode(12)
	tree.root.right.left.right.right = getTreeNode(13)
	/*
	          ↓
	          1 
	         /  \
	      → 11   3  ←
	       /    /  \
	    → 4    5    6  ← 
	     / \    \    \  
	  → 8   7    12   -4  ←
	       / \    \    
	   → -2   9    13 ←

	    --------------------
	    Boundary Nodes
	        
	*/
	tree.findBoundaryLevelNode()
}

Output

1
11  3
4  6
8  -4
-2  13
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Print the boundary nodes in each level of the binary tree
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 Result
{
	public TreeNode first;
	public TreeNode last;
	public Result()
	{
		this.first = null;
		this.last = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	public void findBoundaryNode(TreeNode node, 
                                  Dictionary < int, Result > record, int level)
	{
		if (node != null)
		{
			if (!record.ContainsKey(level))
			{
				record.Add(level, new Result());
			}
			if (record[level].first == null)
			{
				// Collect first node
				record[level].first = node;
			}
			else
			{
				// Collect last node
				record[level].last = node;
			}
			// Visit left subtree
			this.findBoundaryNode(node.left, record, level + 1);
			// Visit right subtree
			this.findBoundaryNode(node.right, record, level + 1);
		}
	}
	public void findBoundaryLevelNode()
	{
		if (this.root == null)
		{
			return;
		}
		Dictionary < int, Result > record =
          new Dictionary < int, Result > ();
		this.findBoundaryNode(this.root, record, 0);
		int level = 0;
		// Display boundary level node
		while (level < record.Count)
		{
			if (record[level].first != null)
			{
				// Display first node of level
				Console.Write(record[level].first.data);
			}
			if (record[level].last != null)
			{
				// Display last node of level
				Console.Write("  " + record[level].last.data);
			}
			Console.Write("\n");
			// Change level
			level++;
		}
	}
	public static void Main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		  Binary Tree
		    -----------------------
		          1
		         /  \
		        11   3
		       /    /  \
		      4    5    6   
		     / \    \    \  
		    8   7    12   -4
		       / \    \  
		     -2   9    13
		*/
		// Add Binary tree nodes
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(11);
		tree.root.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(6);
		tree.root.right.right.right = new TreeNode(-4);
		tree.root.right.left = new TreeNode(5);
		tree.root.left.left = new TreeNode(4);
		tree.root.left.left.left = new TreeNode(8);
		tree.root.left.left.right = new TreeNode(7);
		tree.root.left.left.right.left = new TreeNode(-2);
		tree.root.left.left.right.right = new TreeNode(9);
		tree.root.right.left.right = new TreeNode(12);
		tree.root.right.left.right.right = new TreeNode(13);
		/*
		          ↓
		          1 
		         /  \
		      → 11   3  ←
		       /    /  \
		    → 4    5    6  ← 
		     / \    \    \  
		  → 8   7    12   -4  ←
		       / \    \    
		   → -2   9    13 ←

		    --------------------
		    Boundary Nodes
		        
		*/
		tree.findBoundaryLevelNode();
	}
}

Output

1
11  3
4  6
8  -4
-2  13
<?php
// Php program for
// Print the boundary nodes in each level of the binary tree
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 Result
{
	public $first;
	public $last;
	public	function __construct()
	{
		$this->first = NULL;
		$this->last = NULL;
	}
}
class BinaryTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	public	function findBoundaryNode($node, &$record, $level)
	{
		if ($node != NULL)
		{
			if (!array_key_exists($level, $record))
			{
				$record[$level] = new Result();
			}
			if ($record[$level]->first == NULL)
			{
				// Collect first node
				$record[$level]->first = $node;
			}
			else
			{
				// Collect last node
				$record[$level]->last = $node;
			}
			// Visit left subtree
			$this->findBoundaryNode($node->left, $record, $level + 1);
			// Visit right subtree
			$this->findBoundaryNode($node->right, $record, $level + 1);
		}
	}
	public	function findBoundaryLevelNode()
	{
		if ($this->root == NULL)
		{
			return;
		}
		$record = array();
		$this->findBoundaryNode($this->root, $record, 0);
		$level = 0;
		// Display boundary level node
		while ($level < count($record))
		{
			if ($record[$level]->first != NULL)
			{
				// Display first node of level
				echo($record[$level]->first->data);
			}
			if ($record[$level]->last != NULL)
			{
				// Display last node of level
				echo("  ".$record[$level]->last->data);
			}
			echo("\n");
			// Change level
			$level++;
		}
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        11   3
	       /    /  \
	      4    5    6   
	     / \    \    \  
	    8   7    12   -4
	       / \    \  
	     -2   9    13
	*/
	// Add Binary tree nodes
	$tree->root = new TreeNode(1);
	$tree->root->left = new TreeNode(11);
	$tree->root->right = new TreeNode(3);
	$tree->root->right->right = new TreeNode(6);
	$tree->root->right->right->right = new TreeNode(-4);
	$tree->root->right->left = new TreeNode(5);
	$tree->root->left->left = new TreeNode(4);
	$tree->root->left->left->left = new TreeNode(8);
	$tree->root->left->left->right = new TreeNode(7);
	$tree->root->left->left->right->left = new TreeNode(-2);
	$tree->root->left->left->right->right = new TreeNode(9);
	$tree->root->right->left->right = new TreeNode(12);
	$tree->root->right->left->right->right = new TreeNode(13);
	/*
	          ↓
	          1 
	         /  \
	      → 11   3  ←
	       /    /  \
	    → 4    5    6  ← 
	     / \    \    \  
	  → 8   7    12   -4  ←
	       / \    \    
	   → -2   9    13 ←

	    --------------------
	    Boundary Nodes
	        
	*/
	$tree->findBoundaryLevelNode();
}
main();

Output

1
11  3
4  6
8  -4
-2  13
// Node JS program for
// Print the boundary nodes in each level of the binary tree
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class Result
{
	constructor()
	{
		this.first = null;
		this.last = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	findBoundaryNode(node, record, level)
	{
		if (node != null)
		{
			if (!record.has(level))
			{
				record.set(level, new Result());
			}
			if (record.get(level).first == null)
			{
				// Collect first node
				record.get(level).first = node;
			}
			else
			{
				// Collect last node
				record.get(level).last = node;
			}
			// Visit left subtree
			this.findBoundaryNode(node.left, record, level + 1);
			// Visit right subtree
			this.findBoundaryNode(node.right, record, level + 1);
		}
	}
	findBoundaryLevelNode()
	{
		if (this.root == null)
		{
			return;
		}
		var record = new Map();
		this.findBoundaryNode(this.root, record, 0);
		var level = 0;
		// Display boundary level node
		while (level < record.size)
		{
			if (record.get(level).first != null)
			{
				// Display first node of level
				process.stdout.write("" + record.get(level).first.data);
			}
			if (record.get(level).last != null)
			{
				// Display last node of level
				process.stdout.write("  " + record.get(level).last.data);
			}
			process.stdout.write("\n");
			// Change level
			level++;
		}
	}
}

function main()
{
	var tree = new BinaryTree();
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        11   3
	       /    /  \
	      4    5    6   
	     / \    \    \  
	    8   7    12   -4
	       / \    \  
	     -2   9    13
	*/
	// Add Binary tree nodes
	tree.root = new TreeNode(1);
	tree.root.left = new TreeNode(11);
	tree.root.right = new TreeNode(3);
	tree.root.right.right = new TreeNode(6);
	tree.root.right.right.right = new TreeNode(-4);
	tree.root.right.left = new TreeNode(5);
	tree.root.left.left = new TreeNode(4);
	tree.root.left.left.left = new TreeNode(8);
	tree.root.left.left.right = new TreeNode(7);
	tree.root.left.left.right.left = new TreeNode(-2);
	tree.root.left.left.right.right = new TreeNode(9);
	tree.root.right.left.right = new TreeNode(12);
	tree.root.right.left.right.right = new TreeNode(13);
	/*
	          ↓
	          1 
	         /  \
	      → 11   3  ←
	       /    /  \
	    → 4    5    6  ← 
	     / \    \    \  
	  → 8   7    12   -4  ←
	       / \    \    
	   → -2   9    13 ←

	    --------------------
	    Boundary Nodes
	        
	*/
	tree.findBoundaryLevelNode();
}
main();

Output

1
11  3
4  6
8  -4
-2  13
#  Python 3 program for
#  Print the boundary nodes in each level of the binary tree
class TreeNode :
	#  Data value
	#  Indicates left and right subtree
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class Result :
	def __init__(self) :
		self.first = None
		self.last = None
	

class BinaryTree :
	def __init__(self) :
		self.root = None
	
	def findBoundaryNode(self, node, record, level) :
		if (node != None) :
			if (not(level in record.keys())) :
				record[level] = Result()
			
			if (record.get(level).first == None) :
				#  Collect first node
				record.get(level).first = node
			else :
				#  Collect last node
				record.get(level).last = node
			
			#  Visit left subtree
			self.findBoundaryNode(node.left, record, level + 1)
			#  Visit right subtree
			self.findBoundaryNode(node.right, record, level + 1)
		
	
	def findBoundaryLevelNode(self) :
		if (self.root == None) :
			return
		
		record = dict()
		self.findBoundaryNode(self.root, record, 0)
		level = 0
		#  Display boundary level node
		while (level < len(record)) :
			if (record.get(level).first != None) :
				#  Display first node of level
				print(record.get(level).first.data, end = "")
			
			if (record.get(level).last != None) :
				#  Display last node of level
				print("  ", record.get(level).last.data, end = "")
			
			print(end = "\n")
			#  Change level
			level += 1
		
	

def main() :
	tree = BinaryTree()
	#  Binary Tree
	#    -----------------------
	#          1
	#         /  \
	#        11   3
	#       /    /  \
	#      4    5    6   
	#     / \    \    \  
	#    8   7    12   -4
	#       / \    \  
	#     -2   9    13
	#  Add Binary tree nodes
	tree.root = TreeNode(1)
	tree.root.left = TreeNode(11)
	tree.root.right = TreeNode(3)
	tree.root.right.right = TreeNode(6)
	tree.root.right.right.right = TreeNode(-4)
	tree.root.right.left = TreeNode(5)
	tree.root.left.left = TreeNode(4)
	tree.root.left.left.left = TreeNode(8)
	tree.root.left.left.right = TreeNode(7)
	tree.root.left.left.right.left = TreeNode(-2)
	tree.root.left.left.right.right = TreeNode(9)
	tree.root.right.left.right = TreeNode(12)
	tree.root.right.left.right.right = TreeNode(13)
	#          ↓
	#          1 
	#         /  \
	#      → 11   3  ←
	#       /    /  \
	#    → 4    5    6  ← 
	#     / \    \    \  
	#  → 8   7    12   -4  ←
	#       / \    \    
	#   → -2   9    13 ←
	#    --------------------
	#    Boundary Nodes
	tree.findBoundaryLevelNode()

if __name__ == "__main__": main()

Output

1
11   3
4   6
8   -4
-2   13
#  Ruby program for
#  Print the boundary nodes in each level of the binary tree
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 Result 
	# Define the accessor and reader of class Result
	attr_reader :first, :last
	attr_accessor :first, :last
	def initialize() 
		self.first = nil
		self.last = 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 findBoundaryNode(node, record, level) 
		if (node != nil) 
			if (!record.key?(level)) 
				record[level] = Result.new()
			end

			if (record[level].first == nil) 
				#  Collect first node
				record[level].first = node
			else
 
				#  Collect last node
				record[level].last = node
			end

			#  Visit left subtree
			self.findBoundaryNode(node.left, record, level + 1)
			#  Visit right subtree
			self.findBoundaryNode(node.right, record, level + 1)
		end

	end

	def findBoundaryLevelNode() 
		if (self.root == nil) 
			return
		end

		record = Hash.new()
		self.findBoundaryNode(self.root, record, 0)
		level = 0
		#  Display boundary level node
		while (level < record.size()) 
			if (record[level].first != nil) 
				#  Display first node of level
				print(record[level].first.data)
			end

			if (record[level].last != nil) 
				#  Display last node of level
				print("  ", record[level].last.data)
			end

			print("\n")
			#  Change level
			level += 1
		end

	end

end

def main() 
	tree = BinaryTree.new()
	#  Binary Tree
	#    -----------------------
	#          1
	#         /  \
	#        11   3
	#       /    /  \
	#      4    5    6   
	#     / \    \    \  
	#    8   7    12   -4
	#       / \    \  
	#     -2   9    13
	#  Add Binary tree nodes
	tree.root = TreeNode.new(1)
	tree.root.left = TreeNode.new(11)
	tree.root.right = TreeNode.new(3)
	tree.root.right.right = TreeNode.new(6)
	tree.root.right.right.right = TreeNode.new(-4)
	tree.root.right.left = TreeNode.new(5)
	tree.root.left.left = TreeNode.new(4)
	tree.root.left.left.left = TreeNode.new(8)
	tree.root.left.left.right = TreeNode.new(7)
	tree.root.left.left.right.left = TreeNode.new(-2)
	tree.root.left.left.right.right = TreeNode.new(9)
	tree.root.right.left.right = TreeNode.new(12)
	tree.root.right.left.right.right = TreeNode.new(13)
	#          ↓
	#          1 
	#         /  \
	#      → 11   3  ←
	#       /    /  \
	#    → 4    5    6  ← 
	#     / \    \    \  
	#  → 8   7    12   -4  ←
	#       / \    \    
	#   → -2   9    13 ←
	#    --------------------
	#    Boundary Nodes
	tree.findBoundaryLevelNode()
end

main()

Output

1
11  3
4  6
8  -4
-2  13
import scala.collection.mutable._;
// Scala program for
// Print the boundary nodes in each level of the binary tree
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 Result(var first: TreeNode,
	var last: TreeNode)
{
	def this()
	{
		this(null, null);
	}
}
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	def findBoundaryNode(node: TreeNode, 
                         record: HashMap[Int, Result], 
      level: Int): Unit = {
		if (node != null)
		{
			if (!record.contains(level))
			{
				record.addOne(level, new Result());
			}
			if (record.get(level).get.first == null)
			{
				// Collect first node
				record.get(level).get.first = node;
			}
			else
			{
				// Collect last node
				record.get(level).get.last = node;
			}
			// Visit left subtree
			findBoundaryNode(node.left, record, level + 1);
			// Visit right subtree
			findBoundaryNode(node.right, record, level + 1);
		}
	}
	def findBoundaryLevelNode(): Unit = {
		if (this.root == null)
		{
			return;
		}
		var record: HashMap[Int, Result] = new HashMap[Int, Result]();
		this.findBoundaryNode(this.root, record, 0);
		var level: Int = 0;
		// Display boundary level node
		while (level < record.size)
		{
			if (record.get(level).get.first != null)
			{
				// Display first node of level
				print(record.get(level).get.first.data);
			}
			if (record.get(level).get.last != null)
			{
				// Display last node of level
				print("  " + record.get(level).get.last.data);
			}
			print("\n");
			// Change level
			level += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
		  Binary Tree
		    -----------------------
		          1
		         /  \
		        11   3
		       /    /  \
		      4    5    6   
		     / \    \    \  
		    8   7    12   -4
		       / \    \  
		     -2   9    13
		*/
		// Add Binary tree nodes
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(11);
		tree.root.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(6);
		tree.root.right.right.right = new TreeNode(-4);
		tree.root.right.left = new TreeNode(5);
		tree.root.left.left = new TreeNode(4);
		tree.root.left.left.left = new TreeNode(8);
		tree.root.left.left.right = new TreeNode(7);
		tree.root.left.left.right.left = new TreeNode(-2);
		tree.root.left.left.right.right = new TreeNode(9);
		tree.root.right.left.right = new TreeNode(12);
		tree.root.right.left.right.right = new TreeNode(13);
		/*
		          ↓
		          1 
		         /  \
		      → 11   3  ←
		       /    /  \
		    → 4    5    6  ← 
		     / \    \    \  
		  → 8   7    12   -4  ←
		       / \    \    
		   → -2   9    13 ←

		    --------------------
		    Boundary Nodes
		        
		*/
		tree.findBoundaryLevelNode();
	}
}

Output

1
11  3
4  6
8  -4
-2  13
import Foundation;
// Swift 4 program for
// Print the boundary nodes in each level of the binary tree
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 Result
{
	var first: TreeNode? ;
	var last: TreeNode? ;
	init()
	{
		self.first = nil;
		self.last = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	func findBoundaryNode(_ node: TreeNode? , 
                          _ record : inout[Int : Result], 
      _ level: Int)
	{
		if (node  != nil)
		{
			if (!record.keys.contains(level))
			{
				record[level] = Result();
			}
			if (record[level]?.first == nil)
			{
				// Collect first node
				record[level]?.first = node;
			}
			else
			{
				// Collect last node
				record[level]?.last = node;
			}
			// Visit left subtree
			self.findBoundaryNode(node!.left, &record, level + 1);
			// Visit right subtree
			self.findBoundaryNode(node!.right, &record, level + 1);
		}
	}
	func findBoundaryLevelNode()
	{
		if (self.root == nil)
		{
			return;
		}
		var record: [Int : Result] = [Int : Result ]();
		self.findBoundaryNode(self.root, &record, 0);
		var level: Int = 0;
		// Display boundary level node
		while (level < record.count)
		{
			if (record[level]!.first  != nil)
			{
				// Display first node of level
				print(record[level]!.first!.data, terminator: "");
			}
			if (record[level]!.last  != nil)
			{
				// Display last node of level
				print("  ", record[level]!.last!.data, terminator: "");
			}
			print(terminator: "\n");
			// Change level
			level += 1;
		}
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        11   3
	       /    /  \
	      4    5    6   
	     / \    \    \  
	    8   7    12   -4
	       / \    \  
	     -2   9    13
	*/
	// Add Binary tree nodes
	tree.root = TreeNode(1);
	tree.root!.left = TreeNode(11);
	tree.root!.right = TreeNode(3);
	tree.root!.right!.right = TreeNode(6);
	tree.root!.right!.right!.right = TreeNode(-4);
	tree.root!.right!.left = TreeNode(5);
	tree.root!.left!.left = TreeNode(4);
	tree.root!.left!.left!.left = TreeNode(8);
	tree.root!.left!.left!.right = TreeNode(7);
	tree.root!.left!.left!.right!.left = TreeNode(-2);
	tree.root!.left!.left!.right!.right = TreeNode(9);
	tree.root!.right!.left!.right = TreeNode(12);
	tree.root!.right!.left!.right!.right = TreeNode(13);
	/*
	          ↓
	          1 
	         /  \
	      → 11   3  ←
	       /    /  \
	    → 4    5    6  ← 
	     / \    \    \  
	  → 8   7    12   -4  ←
	       / \    \    
	   → -2   9    13 ←

	    --------------------
	    Boundary Nodes
	        
	*/
	tree.findBoundaryLevelNode();
}
main();

Output

1
11   3
4   6
8   -4
-2   13
// Kotlin program for
// Print the boundary nodes in each level of the binary tree
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 Result
{
	var first: TreeNode ? ;
	var last: TreeNode ? ;
	constructor()
	{
		this.first = null;
		this.last = null;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	fun findBoundaryNode(node: TreeNode ? , 
                         record : HashMap < Int, Result >  , 
                         level : Int): Unit
	{
		if (node != null)
		{
			if (!record.containsKey(level))
			{
				record.put(level, Result());
			}
			if (record.getValue(level).first == null)
			{
				// Collect first node
				record.getValue(level).first = node;
			}
			else
			{
				// Collect last node
				record.getValue(level).last = node;
			}
			// Visit left subtree
			this.findBoundaryNode(node.left, record, level + 1);
			// Visit right subtree
			this.findBoundaryNode(node.right, record, level + 1);
		}
	}
	fun findBoundaryLevelNode(): Unit
	{
		if (this.root == null)
		{
			return;
		}
		val record: HashMap < Int, Result > = HashMap < Int, Result > ();
		this.findBoundaryNode(this.root, record, 0);
		var level: Int = 0;
		// Display boundary level node
		while (level < record.count())
		{
			if (record.getValue(level).first != null)
			{
				// Display first node of level
				print(record.getValue(level).first?.data);
			}
			if (record.getValue(level).last != null)
			{
				// Display last node of level
				print("  " + record.getValue(level).last?.data);
			}
			print("\n");
			// Change level
			level += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinaryTree = BinaryTree();
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        11   3
	       /    /  \
	      4    5    6   
	     / \    \    \  
	    8   7    12   -4
	       / \    \  
	     -2   9    13
	*/
	// Add Binary tree nodes
	tree.root = TreeNode(1);
	tree.root?.left = TreeNode(11);
	tree.root?.right = TreeNode(3);
	tree.root?.right?.right = TreeNode(6);
	tree.root?.right?.right?.right = TreeNode(-4);
	tree.root?.right?.left = TreeNode(5);
	tree.root?.left?.left = TreeNode(4);
	tree.root?.left?.left?.left = TreeNode(8);
	tree.root?.left?.left?.right = TreeNode(7);
	tree.root?.left?.left?.right?.left = TreeNode(-2);
	tree.root?.left?.left?.right?.right = TreeNode(9);
	tree.root?.right?.left?.right = TreeNode(12);
	tree.root?.right?.left?.right?.right = TreeNode(13);
	/*
	          ↓
	          1 
	         /  \
	      → 11   3  ←
	       /    /  \
	    → 4    5    6  ← 
	     / \    \    \  
	  → 8   7    12   -4  ←
	       / \    \    
	   → -2   9    13 ←

	    --------------------
	    Boundary Nodes
	        
	*/
	tree.findBoundaryLevelNode();
}

Output

1
11  3
4  6
8  -4
-2  13


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







© 2021, kalkicode.com, All rights reserved