Binary Tree Algorithm
The Binary Tree Inorder Traversal Algorithm is a depth-first traversal technique used to visit all the nodes in a binary tree in a specific order. In this algorithm, the nodes of the binary tree are visited in the following sequence: first, the left subtree is traversed, then the root node is visited, and finally, the right subtree is traversed. This sequence is applied recursively for each subtree in the binary tree. The result of the inorder traversal is a list of the tree's nodes sorted in ascending order, which makes this algorithm particularly useful when working with binary search trees.
To implement the inorder traversal algorithm, one can use either a recursive or an iterative approach. In the recursive approach, the algorithm first calls itself for the left subtree of the root node, then it processes the root node by adding its value to the resulting list, and finally, it calls itself for the right subtree of the root node. The iterative approach, on the other hand, uses a stack data structure to keep track of the nodes yet to be visited. Starting with the root node, it pushes all the nodes in the left subtree onto the stack, then pops and processes the top node, and repeats the process for the right subtree. This iterative approach can be more efficient in terms of memory usage, as it eliminates the overhead of recursive function calls.
package BinaryTree
type Node struct {
data int
parent *Node
left *Node
right *Node
}
type BinaryTree struct {
root *Node
}
func (tree *BinaryTree) InsertItem(i int) {
if tree.root == nil {
tree.root = &Node{data: i}
return
}
currentNode := tree.root
for {
if i > currentNode.data {
if currentNode.right == nil {
currentNode.right = &Node{data: i, parent: currentNode}
return
}
currentNode = currentNode.right
} else {
if currentNode.left == nil {
currentNode.left = &Node{data: i, parent: currentNode}
return
}
currentNode = currentNode.left
}
}
}
func (tree *BinaryTree) SearchItem(i int) (*Node, bool) {
if tree.root == nil {
return nil, false
}
currentNode := tree.root
for currentNode != nil {
if i == currentNode.data {
return currentNode, true
} else if i > currentNode.data {
currentNode = currentNode.right
} else if i < currentNode.data {
currentNode = currentNode.left
}
}
return nil, false
}
func (tree *BinaryTree) InorderTraversal(subtree *Node, callback func(int)) {
if subtree.left != nil {
tree.InorderTraversal(subtree.left, callback)
}
callback(subtree.data)
if subtree.right != nil {
tree.InorderTraversal(subtree.right, callback)
}
}
func (tree *BinaryTree) PreorderTraversal(subtree *Node, callback func(int)) {
callback(subtree.data)
if subtree.left != nil {
tree.PreorderTraversal(subtree.left, callback)
}
if subtree.right != nil {
tree.PreorderTraversal(subtree.right, callback)
}
}
func (tree *BinaryTree) PostorderTraversal(subtree *Node, callback func(int)) {
if subtree.left != nil {
tree.PostorderTraversal(subtree.left, callback)
}
if subtree.right != nil {
tree.PostorderTraversal(subtree.right, callback)
}
callback(subtree.data)
}
