Top view of binary tree using recursion in swift
Swift program for Top view of binary tree using recursion. Here problem description and explanation.
import Foundation
/*
Swift 4 program for
Top view of binary tree using dfs
*/
// Binary Tree Node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
var level: Int;
init()
{
self.root = nil;
self.level = 0;
}
// Print left side top nodes including root
func printleftSide(_ node: TreeNode? , _ depth : Int)
{
if (node != nil)
{
if (self.level < depth)
{
// Print the resultant node
print(node!.data, terminator: " ");
self.level = depth;
}
// Recursively
// Visit left subtree
self.printleftSide(node!.left, depth + 1);
// Visit right subtree
self.printleftSide(node!.right, depth - 1);
}
}
// Print right side top nodes
func printRightSide(_ node: TreeNode? , _ depth : Int)
{
if (node != nil)
{
if (self.level < depth)
{
// Print the resultant node
print(node!.data, terminator: " ");
self.level = depth;
}
// Recursively
// First visit right subtree
self.printRightSide(node!.right, depth + 1);
// Then
// Visit left subtree
self.printRightSide(node!.left, depth - 1);
}
}
// This is handle the request of printing top view
func topView()
{
self.level = -1;
self.printleftSide(self.root, 0);
self.level = 0;
self.printRightSide(self.root, 0);
}
static func main(_ args: [String])
{
// Create new tree
let tree: BinaryTree? = BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
/ \
7 8
\
9
\
10
*/
// Construct binary tree
tree!.root = TreeNode(1);
tree!.root!.left = TreeNode(2);
tree!.root!.right = TreeNode(3);
tree!.root!.right!.right = TreeNode(6);
tree!.root!.right!.left = TreeNode(5);
tree!.root!.left!.left = TreeNode(4);
tree!.root!.left!.left!.left = TreeNode(7);
tree!.root!.right!.left!.right = TreeNode(8);
tree!.root!.right!.left!.right!.right = TreeNode(9);
tree!.root!.right!.left!.right!.right!.right = TreeNode(10);
// Display top view
tree!.topView();
}
}
BinaryTree.main([String]());
Output
1 2 4 7 3 6 10
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