package main
import "fmt"
var root *Node
type Node struct {
data string
left *Node
right *Node
}
func createNode(data string) *Node {
var node Node
node.data = data
node.left = nil
node.right = nil
return &node
}
func preorder(node *Node) {
if (node != nil) {
fmt.Print(node.data, " ")
preorder(node.left)
preorder(node.right)
}
}
func postorder(node *Node) {
if (node != nil) {
postorder(node.left)
postorder(node.right)
fmt.Print(node.data, " ")
}
}
func inorder(node *Node) {
if (node != nil) {
inorder(node.left)
fmt.Print(node.data, " ")
inorder(node.right)
}
}
func main() {
root = createNode("A")
root.left = createNode("B")
root.right = createNode("C")
root.left.right = createNode("D")
root.right.left = createNode("E")
fmt.Println("Preorder traversal : ")
preorder(root)
fmt.Println()
fmt.Println("Postorder traversal : ")
postorder(root)
fmt.Println()
fmt.Println("Inorder traversal : ")
inorder(root)
fmt.Println()
}
So, in this case we have taken the below Tree and and calculated the Preorder, Postorder and Inorder Traversal for the below Tree.
Just remember, we have used a process called Recursion. Where Go maintains an internal Stack to remember the visited Nodes. So, that the Nodes are not visited twice.
So, we have a Node structure,
type Node struct {
data string
left *Node
right *Node
}To understand the Node structure, let us take any Node and understand it in detail.
Let us take the Node A as example.
So, the Node A has a name i.e A. A Left part that should hold the Left Node i.e. B and a Right part to hold the Right Node i.e. C.
Now, if you look at the Node class. It has String type attribute data string to hold name of the Node i.e. A.
There is also a Node type attribue left *Node that holds the address of left Node of A, i.e. B and there is a Node type attribue right *Node that holds the address of right Node of A, i.e. C.
So, Node A looks somewhat like,
Now, let us see the Tree Traversal in action.
So, at first we construct the Tree,
root = createNode("A")
root.left = createNode("B")
root.right = createNode("C")
root.left.right = createNode("D")
root.right.left = createNode("E")And there is the method func createNode(data string) *Node that helps us create the Nodes.
func createNode(data string) *Node {
var node Node
node.data = data
node.left = nil
node.right = nil
return &node
}And the tree is constructed,
Next, we start the Preorder Traversal,
preorder(root)
And the func preorder(node *Node) method is called, and just remember that we are passing the root Node to the method.
func preorder(node *Node) {
if (node != nil) {
fmt.Print(node.data, " ")
preorder(node.left)
preorder(node.right)
}
}Although, the lines of code looks very less. It is because, the recursion process is doing a lot for us. And it all happens internally, hidden from us.
Let us understand the process in detail.
So, the root Node is A and the node variable has the details of Node A in it.
In the first line we perform a null check
if (node != null)
And then begin the Preorder Traversal. And the rule is Root --> Left --> Right.
i.e. We visit the root element first, then visit all the elements of the Left Sub-Tree and finally, visit all the elements of the Right Sub-Tree.
So, as per the rule we will visit the root Node A and print it first.
fmt.Print(node.data, " ")
So, the result is :
A
Then we are suppose to visit all the elements of the Left Sub-Tree. And thus we call the preorder(...) method from itself, by passing the Left Node i.e. B (As node.left contains B).
preorder(node.left)
Now, the preorder(...) method is called again. And this time Node B becomes the new root element.
And once again the same method is executed with Node B.
func preorder(node *Node) {
if (node != nil) {
fmt.Print(node.data, " ")
preorder(node.left)
preorder(node.right)
}
}Even in this case, as per the Preorder traversal process Root --> Left --> Right. We print the new root element B.
fmt.Print(node.data, " ")
So, the result is :
A B
And once again we call the preorder(...) method.
preorder(node.left)
And this time node.left is nil. Because B has no left element.
So, preorder(...) method is called with the new root element as nil.
func preorder(node *Node) {
if (node != nil) {
fmt.Print(node.data, " ")
preorder(node.left)
preorder(node.right)
}
}And this time node variable is nil. So, the method execution ends here.
if (node != null)
But ! Just Hold on !
The program execution has not yet ended. This is the time when Go starts backtracking.
Don't get scared by the word backtracking. We will understand it eventually.
Now, just think ! The method execution in the above case was not completed. i.e. The line preorder(node.right) never got executed. Well! Go also remembers it.
And Go does a time travel and goes back to the time when the method executed with Node B.
func preorder(node *Node) {
if (node != nil) {
fmt.Print(node.data, " ")
preorder(node.left)
preorder(node.right)
}
}
And executes the unfinished line,
preorder(node.right);
And this time preOrder(...) method is called with Node D.
And same way, Node D would be printed.
fmt.Print(node.data, " ")
So, the result is :
A B D
And since, there are no children of Node D. It is time to complete the unfinished execution, i.e. When Node A was the root element.
func preorder(node *Node) {
if (node != nil) {
fmt.Print(node.data, " ")
preorder(node.left)
preorder(node.right)
}
}And we come to the unfinished line of preorder(...) method.
i.e.
preorder(node.right)
And think logically, we are done with the root element A. Also we are done traversing all the elements of the Left Sub-Tree B. And now, it's time for us to traverse the Right Sub-Tree C.
So, this time the method preorder(...) is called with the root Node C.
func preorder(node *Node) {
if (node != nil) {
fmt.Print(node.data, " ")
preorder(node.left)
preorder(node.right)
}
}
Since the root Node is C. So, we print C.
fmt.Print(node.data, " ")
So, the result is :
A B D C
Then the preOrder(...) method is called with E as root(Since, E is the left child of C).
preorder(node.left)
And the method is called again printing C.
A B D C E
And finally, all the elements are visited and with this we complete the Preorder traversal.
And exactly the same execution pattern follows for the methods :