Skip to main content

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




Comment

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