Print the boundary nodes in each level of the binary tree

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