Skip to main content

Inorder traversal of binary tree using stack in swift

Swift program for Inorder traversal of binary tree using stack. Here problem description and explanation.

import Foundation
// Swift 4 program for
// Inorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	// Make a tree node
	init(_ data: Int)
	{
		// Set node data
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class StackNode
{
	var element: TreeNode? ;
	var next: StackNode? ;
	init(_ element: TreeNode? )
	{
		self.element = element;
		self.next = nil;
	}
}
// Stack Class
class MyStack
{
	var top: StackNode? ;
	var size: Int;
	init()
	{
		self.top = nil;
		self.size = 0;
	}
	// Add new element into stack
	func push(_ element: TreeNode? )
	{
		// Create new node
		let node: StackNode? = StackNode(element);
		node!.next = self.top;
		// new node is new top
		self.top = node;
		// Increase the size
		self.size += 1;
	}
	// Remove top element of the stack
	func pop()
	{
		if (self.top  != nil)
		{
			// next node is new top
			self.top = self.top!.next;
			// Reduce size
			self.size -= 1;
		}
	}
	// Returns the status of empty or non empty stacks
	func isEmpty() -> Bool
	{
		if (self.size > 0 && self.top  != nil)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Return top element of stack
	func peek() -> TreeNode?
	{
		if (self.isEmpty())
		{
			return nil;
		}
		return self.top!.element;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	// Display Inorder view of binary tree
	func inorder()
	{
		if (self.root  != nil)
		{
			// Make new stack
			let s: MyStack? = MyStack();
			var node: TreeNode? = self.root;
			// Display tree element
			while (!s!.isEmpty() || node  != nil)
			{
				if (node  != nil)
				{
					// Add current node
					s!.push(node);
					// Visit to left subtree
					node = node!.left;
				}
				else
				{
					// When node is null
					// Get stack top element
					node = s!.peek();
					// Display node value
					print(node!.data, terminator: "  ");
					// Remove top element of the stack
					s!.pop();
					// Visit to left subtree of current node
					node = node!.right;
				}
			}
		}
		else
		{
			print("Empty Linked List");
		}
	}
	static func main(_ args: [String])
	{
		// Create new tree
		let tree: BinaryTree? = BinaryTree();
		/*
		    Construct Binary Tree
		    -----------------------
		        15
		       /  \
		      24   54
		     /    /  \
		    35   62   13
		*/
		// Add tree nodes
		tree!.root = TreeNode(15);
		tree!.root!.left = TreeNode(24);
		tree!.root!.right = TreeNode(54);
		tree!.root!.right!.right = TreeNode(13);
		tree!.root!.right!.left = TreeNode(62);
		tree!.root!.left!.left = TreeNode(35);
		// Display result
		tree!.inorder();
	}
}
BinaryTree.main([String]());

Output

35  24  15  62  54  13




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