Golang – Preorder Tree Traversal
Here in this article, we shall discuss steps and different approach of implementing preorder tree traversal. You can get the preorder tree traversal in java in our article Preorder Tree Traversal (DFS) in java. There are two ways, iterative and recursive for preorder tree traversal.We follow below steps for traversal
1) Visit the root.
2) Traverse the left subtree, i.e., call Preorder(left-subtree)
3) Traverse the right subtree, i.e., call Preorder(right-subtree)
Preorder Traversal of above tree is 10, 20, 40, 70, 50, 30, 60
Time Complexity: O(n)
Recursive solution for Preorder Tree Traversal :
Algorithm for recursive solution is
|
1 2 3 |
1) Print root node 2) Traversal left node i.e preorder(root.left) 3) Traversal right node i.e preorder(root.right) |
Code for recursive solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
package main import ( "fmt" ) type Node struct { val int left *Node right *Node } func PreorderRecursive(root *Node) { if root != nil { fmt.Printf("%d ", root.val) PreorderRecursive(root.left) PreorderRecursive(root.right) } } func main() { /* 10 / \ 20 30 / \ \ 40 50 60 / 70 */ root := &Node{10, nil, nil} root.left = &Node{20, nil, nil} root.right = &Node{30, nil, nil} root.left.left = &Node{40, nil, nil} root.left.right = &Node{50, nil, nil} root.right.right = &Node{60, nil, nil} root.left.left.left = &Node{70, nil, nil} fmt.Println("Preorder Traversal - Recursive Solution : ") PreorderRecursive(root) } |
Output
|
1 2 |
Preorder Traversal - Recursive Solution : 10 20 40 70 50 30 60 |
Iterative solution for Preorder Traversal
To implement iterative solution for Preorder Traversal, we will be using Stack data structure. Use “go get github.com/emirpasic/gods/stacks/arraystack” to get stack.
Algorithm for iterative solution is
|
1 2 3 4 5 |
1) Push the root to the stack 2) while stack is not empty do the following - pop the top node and print it. - push the right node of the popped node to the stack. - push the left node of the popped node to the stack. |
Code for iterative solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
package main import ( "fmt" "github.com/emirpasic/gods/stacks/arraystack" ) type Node struct { val int left *Node right *Node } func PreorderIterative(root *Node) { if root == nil { return } current := root stack := arraystack.New() stack.Push(current) for stack.Size() > 0 { temp, _ := stack.Pop() current = temp.(*Node) fmt.Printf("%d ", current.val) if current.right != nil { stack.Push(current.right) } if current.left != nil { stack.Push(current.left) } } } func main() { /* 10 / \ 20 30 / \ \ 40 50 60 / 70 */ root := &Node{10, nil, nil} root.left = &Node{20, nil, nil} root.right = &Node{30, nil, nil} root.left.left = &Node{40, nil, nil} root.left.right = &Node{50, nil, nil} root.right.right = &Node{60, nil, nil} root.left.left.left = &Node{70, nil, nil} fmt.Println("Preorder Traversal - Iterative Solution : ") PreorderIterative(root) } |
Output
|
1 2 |
Preorder Traversal - Iterative Solution : 10 20 40 70 50 30 60 |
Stay tuned for more updates and tutorials !!!