Skip to main content

Inorder traversal of binary tree using stack in golang

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

package main
import "fmt"
// Go program for
// Inorder traversal without recursion
// Using stack

// Binary Tree node
type TreeNode struct {
    data int
    left * TreeNode
    right * TreeNode
}
func getTreeNode(data int) * TreeNode {
    return &TreeNode {data,nil,nil}
}
type StackNode struct {
    element * TreeNode
    next * StackNode
}
func getStackNode(element * TreeNode) * StackNode {
    return &StackNode {element,nil}
}
// Stack Class
type MyStack struct {
    top * StackNode
    size int
}
func getMyStack() * MyStack {
    return &MyStack {nil,0}
}
// Add new element into stack
func(this *MyStack) push(element * TreeNode) {
    // Create new node
    var node * StackNode = getStackNode(element)
    node.next = this.top
    // new node is new top
    this.top = node
    // Increase the size
    this.size += 1
}
// Remove top element of the stack
func(this *MyStack) pop() {
    if this.top != nil {
        // next node is new top
        this.top = this.top.next
        // Reduce size
        this.size -= 1
    }
}
// Returns the status of empty or non empty stacks
func(this MyStack) isEmpty() bool {
    if this.size > 0 && this.top != nil {
        return false
    } else {
        return true
    }
}
// Return top element of stack
func(this MyStack) peek() * TreeNode {
    if this.isEmpty() {
        return nil
    }
    return this.top.element
}
type BinaryTree struct {
    root * TreeNode
}
func getBinaryTree() * BinaryTree {
    return &BinaryTree {nil}
}
// Display Inorder view of binary tree
func(this BinaryTree) inorder() {
    if this.root != nil {
        // Make new stack
        var s * MyStack = getMyStack()
        var node * TreeNode = this.root
        // Display tree element
        for (!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
                fmt.Print(" ", node.data)
                // Remove top element of the stack
                s.pop()
                // Visit to left subtree of current node
                node = node.right
            }
        }
    } else {
        fmt.Print("Empty Linked List\n")
    }
}
func main() {
    // Create new tree
    var tree * BinaryTree = getBinaryTree()
    /*
        Construct Binary Tree
        -----------------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree nodes
    tree.root = getTreeNode(15)
    tree.root.left = getTreeNode(24)
    tree.root.right = getTreeNode(54)
    tree.root.right.right = getTreeNode(13)
    tree.root.right.left = getTreeNode(62)
    tree.root.left.left = getTreeNode(35)
    // Display result
    tree.inorder()
}

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