Last active
September 19, 2022 01:40
-
-
Save maxclav/762e00a455b14733ae63b55d66585946 to your computer and use it in GitHub Desktop.
Binary Tree Depth-First Search (DFS) Traversals in Go (GoLang).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package binarytree | |
// Tree is a binary tree. | |
type Tree struct { | |
Root *Node | |
} | |
// Node is a binary tree node. | |
type Node struct { | |
Val int | |
Left *Node | |
Right *Node | |
} | |
// DFSPostorderTraversal uses Depth-First Search (DFS) | |
// to return the postorder traversal of the tree nodes. | |
func DFSPostorderTraversal(t *Tree) []int { | |
sol := make([]int, 0) | |
if t == nil || t.Root == nil { | |
return sol | |
} | |
return postorderTraversal(t.Root, sol) | |
} | |
func postorderTraversal(n *Node, traversed []int) []int { | |
if n == nil { | |
return traversed | |
} | |
traversed = postorderTraversal(n.Left, traversed) | |
traversed = postorderTraversal(n.Right, traversed) | |
traversed = append(traversed, n.Val) | |
return traversed | |
} | |
// DFSPreorderTraversal uses Depth-First Search (DFS) | |
// to return the preorder traversal of the tree nodes. | |
func DFSPreorderTraversal(t *Tree) []int { | |
sol := make([]int, 0) | |
if t == nil || t.Root == nil { | |
return sol | |
} | |
return preorderTraversalWith(t.Root, sol) | |
} | |
func preorderTraversalWith(n *Node, traversed []int) []int { | |
if n == nil { | |
return traversed | |
} | |
traversed = append(traversed, n.Val) | |
traversed = preorderTraversalWith(n.Left, traversed) | |
traversed = preorderTraversalWith(n.Right, traversed) | |
return traversed | |
} | |
// DFSInorderTraversal uses Depth-First Search (DFS) | |
// to return the inorder traversal of the tree nodes. | |
func DFSInorderTraversal(t *Tree) []int { | |
sol := make([]int, 0) | |
if t == nil || t.Root == nil { | |
return sol | |
} | |
return inorderTraversal(t.Root, sol) | |
} | |
func inorderTraversal(n *Node, traversed []int) []int { | |
if n == nil { | |
return traversed | |
} | |
traversed = inorderTraversal(n.Left, traversed) | |
traversed = append(traversed, n.Val) | |
traversed = inorderTraversal(n.Right, traversed) | |
return traversed | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package binarytree | |
import "fmt" | |
// Here is an example | |
func main() { | |
t := &Tree{ | |
Root: &Node{ | |
Val: 1, | |
Left: &Node{ | |
Val: 2, | |
Left: &Node{ | |
Val: 3, | |
}, | |
Right: &Node{ | |
Val: 4, | |
}, | |
}, | |
Right: &Node{ | |
Val: 5, | |
}, | |
}, | |
} | |
fmt.Println(DFSPostorderTraversal(t)) // [3 4 2 5 1] | |
fmt.Println(DFSPreorderTraversal(t)) // [1 2 3 4 5] | |
fmt.Println(DFSInorderTraversal(t)) // [3 2 4 1 5] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
In
![Screen Shot 2022-09-18 at 10 41 04 AM](https://user-images.githubusercontent.com/14335619/190920974-27a3ee83-ba04-4e50-be00-e0c8a30bff43.png)
main.go
, we built this tree:And here are the different traversals of this tree:
See "Binary Tree Breadth-First Search (BFS) Traversal using a queue in Go (GoLang)" HERE.