Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Print Spiral Tree

Explore how to print nodes of a binary tree in spiral order by using two stacks in Go. Understand the LIFO principle application, step through the code, and analyze time and space complexity to enhance your tree traversal skills.

We'll cover the following...

Solution

Stacks follow the LIFO principle, so two stacks are used to process each level alternatively. The nodes are added and processed in such an order that nodes are printed in spiral order. Let’s look at how we can do this in code.

Solution code

Go (1.6.2)
package main
import "fmt"
func (t *Tree) PrintSpiralTree() {
    stk1 := new(Stack)
    stk2 := new(Stack)
    var temp *Node
    if t.root != nil {
        stk1.Push(t.root)
    }
    for stk1.Length() != 0 || stk2.Length() != 0 {
        for stk1.Length() != 0 {
            temp = stk1.Pop()
            fmt.Print(temp.value, " ")
            if temp.left != nil {
                stk2.Push(temp.left)
            }
            if temp.right != nil {
                stk2.Push(temp.right)
            }
        }
        fmt.Println(" ")
        for stk2.Length() != 0{
            temp = stk2.Pop()
            fmt.Print(temp.value, " ")
            if temp.right != nil {
                stk1.Push(temp.right)
            }
            if temp.left != nil {
                stk1.Push(temp.left)
            }
        }
        fmt.Println(" ")
    }
}
/* Testing Code */
func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    t := LevelOrderBinaryTree(arr)
    t.PrintSpiralTree()
}

Complexity analysis

The time and space complexity of this solution is ...